Some housekeeping (again), installing necessary packages.

list.of.packages <- c("igraph", "tidygraph", "ggraph")
new.packages <- list.of.packages[!(list.of.packages %in% installed.packages()[,"Package"])]
if(length(new.packages)) install.packages(new.packages)
rm(list.of.packages, new.packages)

Introduction

Welcome to Module 2. This script is available as R-notebook (pretty) as well as executable jupyter notebook on kaggle here. HAve fun!

Networks… So what?

So, before we talk about networks, one thing upfront… why should we? I mean, they undeniably look pretty, don’t they?

Somehow, the visualization of networks fascinates the human mind (find a short TED talk on networks and how they depict our world here), and has even inspired an own art movement, networkism (see some examples here).

Yet, besides that, is there an analytical value for a data scientist to bother about networks?

Networks in R

There are a number of applications designed for network analysis and the creation of network graphs such as gephi and cytoscape. Though not specifically designed for it, R has developed into a powerful tool for network analysis.

Significant network analysis packages for R include the network, sna, and igraph package. In addition, Thomas Lin Pedersen has recently released the tidygraph package that leverage the power of igraph in a manner consistent with the tidyverse workflow. Even better, he tops it up with ggraph, a consistent ´ggplot2´-look-and-feel network visualization package.

R can also be used to make interactive network graphs with the htmlwidgets framework that translates R code to JavaScript. Cool implementations thereof are the vizNetwork and networkD3 packages.

As analytical tool, I will in this lab mostly use igraph. In terms of functions, it is pretty much equivalent to network, yet slightly more powerful, better integrated, and maintained. Since both packages have many of the same functions, better don’t load them both at once.

The Basic Structure of Networks

The Basic Jargon

First of all, what is a network? Plainly speaking, a network is a system of elements which are connected by some relationship. The vocabulary can be a bit technical and even inconsistent between different disciplines, packages, and software. The whole system is (surprise, surprise) usually called a network or graph. The elements are commonly referred to as nodes (system theory jargon) or vertices (graph theory jargon) of a graph, while the connections are edges or links. I will mostly refer to the elements as nodes, and their connections as edges.

Generally, networks are a form of representing relational data. This is a very general tool that can be applied to many different types of relationships between all kind of elements. The content, meaning, and interpretation for sure depends on what elements we display, and which types of relationships. For example:

  • In Social Network Analysis:
    • Nodes represent actors (which can be persons, firms and other socially constructed entities)
    • Edges represent relationships between this actors (friendship, interaction, co-affiliation, similarity ect.)
  • Other types of network
    • Chemistry: Interaction between molecules
    • Computer Science: The wirld-wide-web, inter- and intranet topologies
    • Biology: Food-web, ant-hives

The possibilities to depict relational data are manifold. For example:

  • Relations among persons
    • Kinship: mother of, wife of…
    • Other role based: boss of, supervisor of…
    • Cognitive/perceptual: knows, aware of what they know…
    • Affective: likes, trusts…
    • Interaction: give advice, talks to…
    • Affiliation: belong to same clubs, shares same interests…
  • Relations among organizations
    • As corporate entities
    • Buy from / sell to, leases to, outsources to
    • Owns shares of, subsidiary of
    • Joint ventures, strategic alliances
    • Via their members
      • Personnel flows
      • Interlocking directorates
      • Personal friendships
      • Co-memberships
  • Relations other (non-social) entities
    • Patents
      • Patents citing other patents
      • Co-occurrence of technological classes *Research fields
      • through citations
      • through people co-affiliated with fields *Sectors
      • input-output relations
      • Labor mobility *Technologies
      • Patent IPC classes
      • Semantic co-occurrence

Note: Content matters! Each relation yields a different structure & has different effects. Theories might make sense on inter-personal, but not inter-organizational or non-social context.

The Data-Structure of Relational Data

Edgelist

MOst real world relational data is to be found in what we call an edge list, a dataframe that contains a minimum of two columns, one column of nodes that are the source of a connection and another column of nodes that are the target of the connection. The nodes in the data are identified by unique IDs. If the distinction between source and target is meaningful, the network is directed. If the distinction is not meaningful, the network is undirected (more on that later). So, every row that contains the ID of one element in column 1, and the ID of another element in column 2 indicates that a connection between them exists. An edge list can also contain additional columns that describe attributes of the edges such as a magnitude aspect for an edge. If the edges have a magnitude attribute the graph is considered weighted (more on that later). Below an example ofa minimal edge list created with the tibble() function.

edge_list <- tibble(from = c(1, 2, 2, 3, 4), to = c(2, 3, 4, 2, 1))
edge_list

Sometimes it is preferable to also create a separate node list. At its simplest, a node list is a data frame with a single column - which I will label as “id” - that lists the node IDs found in the edge list. The advantage of creating a separate node list is the ability to add attribute columns to the data frame such as the names of the nodes or any kind of groupings.

library(tidyverse)
node_list <- tibble(id = 1:4, group = sample(letters[1:2], 4, replace = TRUE))
node_list

Adjacency Matrix

A second popular form of network representation is the adjacency-matrix (also called socio-matrix). It is represented as a \(n*n\) matrix, where \(n\) stands for the number of elements of which their relationships should be represented. The value in the cell that intercepts row \(n\) and column \(m\) indicates if an edge is present (=1) or absent (=0).

Tip: Given an edgelist, an adjacency matrix can easily be produced by crosstabulating:

adj_matrix <- table(edge_list) %>% as.matrix()
adj_matrix
    to
from 1 2 3 4
   1 0 1 0 0
   2 0 0 1 1
   3 0 1 0 0
   4 1 0 0 0

Generating a Graph Object in igraph

To create an igraph object from an edge-list data frame we can use the graph_from_data_frame() function, which is a bit more straight forward than network(). There are three arguments in the graph_from_data_frame() function: d, vertices, and directed. Here, d refers to the edge list, vertices to the node list, and directed can be either TRUE or FALSE depending on whether the data is directed or undirected. By default, graph.data.frame() treats the first two columns of the edge list and any remaining columns as edge attributes.

library(igraph)
g <- graph_from_data_frame(d = edge_list, vertices = node_list, directed = FALSE)
g
IGRAPH 9a7dc23 UN-- 4 5 -- 
+ attr: name (v/c), group (v/c)
+ edges from 9a7dc23 (vertex names):
[1] 1--2 2--3 2--4 2--3 1--4

Lets inspect the resulting object. An igraph graph object summary reveals some interesting informations.

  • First, it tells us the graph-type: undirected UN, or directed DN
  • Afterwards, the number of nodes (4), and edges (6)
  • Followed by the node attributes (node level variables), which in this case are only their name (attr: name (v/c))
  • Lastly, a list of all existing edges. Note: n--m indicates an undirected, n->m an directed edge.

Lets take a look at the structure of the object:

glimpse(g[[1]])
List of 1
 $ 1: 'igraph.vs' Named int [1:2] 2 4
  ..- attr(*, "names")= chr [1:2] "2" "4"
  ..- attr(*, "env")=<weakref> 
  ..- attr(*, "graph")= chr "9a7dc23d-c68d-11e8-bf15-71dbd5073803"

We see, the object has a list-format, consisting of sepperate lists for every node, containing some attributes which are irrelevant now, and an edgelist for every node, capturing its ego-network (eg., .. ..- attr(*, "names")= chr [1:2] "2" "4")

We can also plot it to take a look. igraph object can be directly used with the plot() function. The results can be adjusted with a set of parameters we will discover later. It’s not super pretty, therefore we will later also explore more powerfull plotting tools for rgaphs. However, its quick&dirty, so lets take it like that for now.

plot(g)

Yeah, that’s the graph. We We can also use the adjacency matrix to create the same graph.

g <- graph_from_adjacency_matrix(adj_matrix, mode = "undirected")
g
IGRAPH 9f8ef31 UN-- 4 4 -- 
+ attr: name (v/c)
+ edges from 9f8ef31 (vertex names):
[1] 1--2 1--4 2--3 2--4

We can inspect and manipulate the nodes via V(g) (V for vertices, its graph-theory slang), and edges with E(g)

V(g)
+ 4/4 vertices, named, from 9f8ef31:
[1] 1 2 3 4
E(g)
+ 4/4 edges from 9f8ef31 (vertex names):
[1] 1--2 1--4 2--3 2--4

We can also use most of the base-R slicing&dicing.

V(g)[1:3]
+ 3/4 vertices, named, from 9f8ef31:
[1] 1 2 3
E(g)[2:4]
+ 3/4 edges from 9f8ef31 (vertex names):
[1] 1--4 2--3 2--4

Remember, it’s a list-object. So, if we just want to have the values, we have to use the double bracket [[x]].

V(g)[[1:3]]
+ 3/4 vertices, named, from 9f8ef31:

We can also use the $ notation.

V(g)$name
[1] "1" "2" "3" "4"

Networks are coming…

So, lets get serious. Appropriate for the weather these days in Denmark, the theme is “winter is comming…”. Therefore, we will have some fun analysing the Game of Thrones data provided by Andrew Beveridge. It is a Character Interaction Networks for George R. R. Martin’s “A Song of Ice and Fire” saga (yes, we are talking about the books…). These networks were created by connecting two characters whenever their names (or nicknames) appeared within 15 words of one another in one of the books in “A Song of Ice and Fire.” The edge weight corresponds to the number of interactions. THis is a nice skill you will have afeter the second part of M2 on your own.

Build the graph

So, that’s what we have, a classical edgelist, with id1 in column 1 and id2 in column2. Note, the edges are in this case weighted.I don’t like the sepperating “-” between in the names, lets get rid of them.

colnames(edges.cooc.all) <- tolower(colnames(edges.cooc.all))
edges.cooc.all %<>%
  mutate(source = gsub("-", " ", source),
         target = gsub("-", " ", target)) 

Ok, lets see how many characters we have overal.

edges.cooc.all %>%
  select(-type) %>%
  gather(x, name, source:target) %>% 
  n_distinct(.$name)
[1] 5646

That’s a lot. We might want to restrict ourselfes first to a small set of the 50 most connected nodes.

chars.main <- edges.cooc.all %>%
  select(-type) %>%
  gather(x, name, source:target) %>%
  group_by(name) %>%
  summarise(sum_weight = sum(weight)) %>%
  ungroup() %>%
  arrange(desc(sum_weight)) %>%
  top_n(50)
head(chars.main)

So far so good, if we only go by edge weights, Seems as if Tyrion might make it…. my favorite anyhow. Lets reduce our edgelist to this main characters, just to warm up and keep the overview.

edges.cooc <- edges.cooc.all %>%
  filter(source %in% chars.main$name & target %in% chars.main$name) %>%
  select(source, target, weight)
g <- graph_from_data_frame(d = edges.cooc, directed = FALSE)
g
IGRAPH 1d7d516 UNW- 50 402 -- 
+ attr: name (v/c), weight (e/n)
+ edges from 1d7d516 (vertex names):
 [1] Aemon Targaryen (Maester Aemon)--Grenn             Aemon Targaryen (Maester Aemon)--Jeor Mormont     
 [3] Aemon Targaryen (Maester Aemon)--Jon Snow          Aemon Targaryen (Maester Aemon)--Mance Rayder     
 [5] Aemon Targaryen (Maester Aemon)--Robert Baratheon  Aemon Targaryen (Maester Aemon)--Samwell Tarly    
 [7] Aemon Targaryen (Maester Aemon)--Stannis Baratheon Arya Stark                     --Bran Stark       
 [9] Arya Stark                     --Catelyn Stark     Arya Stark                     --Cersei Lannister 
[11] Arya Stark                     --Eddard Stark      Arya Stark                     --Gregor Clegane   
[13] Arya Stark                     --Ilyn Payne        Arya Stark                     --Jaime Lannister  
[15] Arya Stark                     --Joffrey Baratheon Arya Stark                     --Jon Snow         
+ ... omitted several edges

Note that this co-occurence network is weighted (number of co-occurence), and undirected.

is_weighted(g)
[1] TRUE
is_directed(g)
[1] FALSE

Inspect the graph

Overal graph attributes

We already know from the summary, but we can also count the number of nodes and edges as follows:

# Count number of edges
gsize(g)
[1] 402
# Count number of vertices
gorder(g)
[1] 50

We can give the graph a first plot to see what happens there. It’s not pretty, but we will fine-tune it later.

plot(g,
     edge.width = (E(g)$weight / max(E(g)$weight)) * 5  # Only argument we use so far for the weighted edges
     )

IS really not pretty. But we will work on that later. However, we already see that some nodes are not connected (isolated), so lets drop them for our network analysis. Lets also get rid of edges with super small weight.

g <- delete_edges(g, E(g)[weight < 20])
g <- delete_vertices(g, degree(g) == 0)

Edges

Lets see a bit which options we have to select edges. We could for example use inc() to select only edges that include a certain node.

Note: Almost all edge and many furtehr graph functions to follow, have an argument called mode. Here, it doesn’t matter, since we ahve an undirected network. In case the edges are directed, we want to specify which mode to consider (mode = c("all", "out", "in", "total")). More on that at a later point.

E(g)[[inc("Daenerys Targaryen")]]  
+ 6/189 edges from daa37c6 (vertex names):

We could also select them due to their characteristics

E(g)[[weight >= 150]]
+ 11/189 edges from daa37c6 (vertex names):

Or plot their weight distribution

hist(E(g)$weight)

There is muchg more, but lets leave it with that for now.

Nodes

The node level gives us the opportunity to select (in this case) certain characters, their connectivity characteristics, and their enviroment.

First we look at different measures of degree-centrality, which are a set of measures incicating a certain type of structural importance in the network.

Degree centrality

The first one is the degree centralities is the degree centrality, which plainly means how well connected the node is (= Number of Edges). The version for the weighted networks (= Sum of edgeweigths) can be accessed with strength(). We can also directly check which node has the maximum degree.

degree(g) 
Aemon Targaryen (Maester Aemon)                      Arya Stark                 Barristan Selmy 
                              3                               9                               5 
                     Bran Stark                Brienne of Tarth                           Bronn 
                             14                               4                               2 
                  Catelyn Stark                Cersei Lannister              Daenerys Targaryen 
                             16                              20                               6 
                 Davos Seaworth                           Drogo                    Eddard Stark 
                              2                               2                              18 
                   Edmure Tully                  Gregor Clegane                           Grenn 
                              3                               4                               2 
               Hizdahr zo Loraq                           Hodor                      Ilyn Payne 
                              2                               4                               4 
                Jaime Lannister                    Jeor Mormont               Joffrey Baratheon 
                             16                               4                              19 
                     Jojen Reed                        Jon Snow                   Jorah Mormont 
                              3                              13                               3 
                   Loras Tyrell                           Luwin                      Lysa Arryn 
                              6                               6                               4 
                   Mance Rayder                 Margaery Tyrell                      Meera Reed 
                              1                               5                               3 
                     Melisandre                     Meryn Trant              Myrcella Baratheon 
                              3                               3                               3 
                  Petyr Baelish                         Pycelle                 Renly Baratheon 
                             10                               6                              10 
                   Rickon Stark                      Robb Stark                Robert Baratheon 
                              6                              17                              16 
                  Rodrik Cassel                   Samwell Tarly                  Sandor Clegane 
                              5                               5                               6 
                    Sansa Stark               Stannis Baratheon                   Theon Greyjoy 
                             17                              13                               6 
               Tommen Baratheon                Tyrion Lannister                 Tywin Lannister 
                              6                              25                               9 
                Quentyn Martell                           Varys 
                              2                               7 
which.max(degree(g))
Tyrion Lannister 
              47 
strength(g)
Aemon Targaryen (Maester Aemon)                      Arya Stark                 Barristan Selmy 
                            234                             512                             226 
                     Bran Stark                Brienne of Tarth                           Bronn 
                           1206                             225                             160 
                  Catelyn Stark                Cersei Lannister              Daenerys Targaryen 
                            766                            1438                             547 
                 Davos Seaworth                           Drogo                    Eddard Stark 
                            195                             151                            1175 
                   Edmure Tully                  Gregor Clegane                           Grenn 
                            128                             102                             121 
               Hizdahr zo Loraq                           Hodor                      Ilyn Payne 
                            138                             333                             112 
                Jaime Lannister                    Jeor Mormont               Joffrey Baratheon 
                            862                             277                            1343 
                     Jojen Reed                        Jon Snow                   Jorah Mormont 
                            223                            1238                             216 
                   Loras Tyrell                           Luwin                      Lysa Arryn 
                            167                             238                             179 
                   Mance Rayder                 Margaery Tyrell                      Meera Reed 
                            112                             258                             255 
                     Melisandre                     Meryn Trant              Myrcella Baratheon 
                            208                             102                              87 
                  Petyr Baelish                         Pycelle                 Renly Baratheon 
                            477                             193                             448 
                   Rickon Stark                      Robb Stark                Robert Baratheon 
                            263                             966                            1091 
                  Rodrik Cassel                   Samwell Tarly                  Sandor Clegane 
                            137                             472                             259 
                    Sansa Stark               Stannis Baratheon                   Theon Greyjoy 
                           1059                             771                             239 
               Tommen Baratheon                Tyrion Lannister                 Tywin Lannister 
                            337                            1694                             392 
                Quentyn Martell                           Varys 
                             80                             400 
which.max(strength(g))
Tyrion Lannister 
              47 

Well, again Tyrion it is…

Eigenvector Centrality

Again, the eigenvector. Eigenvector centrality is a very interesting measure. The idea is that nodes are the more important when they are connected to more important nodes. So, if you have cool friends, you are also supposed to be somewhat cooler. You already see, the calculation of such values in a network becomes circular, therefore we need some mathematical magic, which the eigenvector does. We will dig into this concept deeper at another point. We scale it, since these values otherwise tend to become very large.

Note: Here, also a weighted version is available. Again, the ? is your friend.

eigen_centrality(g, scale = TRUE)$vector %>% round(3)
Aemon Targaryen (Maester Aemon)                      Arya Stark                 Barristan Selmy 
                          0.064                           0.332                           0.073 
                     Bran Stark                Brienne of Tarth                           Bronn 
                          0.297                           0.126                           0.183 
                  Catelyn Stark                Cersei Lannister              Daenerys Targaryen 
                          0.415                           0.952                           0.039 
                 Davos Seaworth                           Drogo                    Eddard Stark 
                          0.060                           0.007                           0.754 
                   Edmure Tully                  Gregor Clegane                           Grenn 
                          0.067                           0.072                           0.035 
               Hizdahr zo Loraq                           Hodor                      Ilyn Payne 
                          0.008                           0.079                           0.086 
                Jaime Lannister                    Jeor Mormont               Joffrey Baratheon 
                          0.547                           0.113                           0.922 
                     Jojen Reed                        Jon Snow                   Jorah Mormont 
                          0.046                           0.364                           0.038 
                   Loras Tyrell                           Luwin                      Lysa Arryn 
                          0.112                           0.061                           0.121 
                   Mance Rayder                 Margaery Tyrell                      Meera Reed 
                          0.047                           0.200                           0.051 
                     Melisandre                     Meryn Trant              Myrcella Baratheon 
                          0.065                           0.089                           0.067 
                  Petyr Baelish                         Pycelle                 Renly Baratheon 
                          0.353                           0.156                           0.267 
                   Rickon Stark                      Robb Stark                Robert Baratheon 
                          0.098                           0.428                           0.755 
                  Rodrik Cassel                   Samwell Tarly                  Sandor Clegane 
                          0.044                           0.127                           0.186 
                    Sansa Stark               Stannis Baratheon                   Theon Greyjoy 
                          0.723                           0.367                           0.091 
               Tommen Baratheon                Tyrion Lannister                 Tywin Lannister 
                          0.270                           1.000                           0.333 
                Quentyn Martell                           Varys 
                          0.004                           0.345 

Betweenness Centrality

Lastly, the betweenness centrality. That is also an very interesting concept. This one is a measure of how much a node connects otherwise unconnected nodes with each others. This is measured by the amount of shortest paths leading through the node.

betweenness(g)

Neighborhood of a Node

Lastly, we can look at the surrounding of a node, meaning the ones it is connected to, its neighborhood.

neighbors(g, 'Robert Baratheon')
+ 16/50 vertices, named, from 17b0991:
 [1] Barristan Selmy    Catelyn Stark      Cersei Lannister   Daenerys Targaryen Eddard Stark      
 [6] Jaime Lannister    Joffrey Baratheon  Jon Snow           Petyr Baelish      Pycelle           
[11] Renly Baratheon    Sansa Stark        Stannis Baratheon  Tyrion Lannister   Tywin Lannister   
[16] Varys             

Likewise, we can look at the ego-network of a node. That means how many nodes are in a certain geodesic distance. Plainly speaking, how many nodes are not more than x-steps away.

ego(g, 2, "Drogo")[[1]]
+ 8/50 vertices, named, from 17b0991:
[1] Drogo              Daenerys Targaryen Jorah Mormont      Barristan Selmy    Hizdahr zo Loraq   Robert Baratheon  
[7] Quentyn Martell    Tyrion Lannister  

We can also not only look at it, but produce a new sub-graph only of this ego-network.

g.drogo <- make_ego_graph(g, 2, nodes = "Drogo")[[1]]
g.danny <- make_ego_graph(g, 2, nodes = "Daenerys Targaryen")[[1]]
plot(g.drogo)

plot(g.danny)

Well, Danny seems to be way more connected than her husband, right?

Btw: To merge two graphs, just do:

g.merge
IGRAPH 45a00e4 UN-- 21 82 -- 
+ attr: name (v/c), weight_1 (e/n), weight_2 (e/n)
+ edges from 45a00e4 (vertex names):
 [1] Stannis Baratheon--Tywin Lannister   Renly Baratheon  --Stannis Baratheon Pycelle          --Varys            
 [4] Petyr Baelish    --Varys             Petyr Baelish    --Sansa Stark       Petyr Baelish    --Pycelle          
 [7] Jon Snow         --Stannis Baratheon Joffrey Baratheon--Varys             Joffrey Baratheon--Tywin Lannister  
[10] Joffrey Baratheon--Stannis Baratheon Joffrey Baratheon--Sansa Stark       Joffrey Baratheon--Renly Baratheon  
[13] Joffrey Baratheon--Petyr Baelish     Jaime Lannister  --Tywin Lannister   Jaime Lannister  --Sansa Stark      
[16] Jaime Lannister  --Renly Baratheon   Jaime Lannister  --Joffrey Baratheon Eddard Stark     --Varys            
[19] Eddard Stark     --Stannis Baratheon Eddard Stark     --Sansa Stark       Eddard Stark     --Renly Baratheon  
[22] Eddard Stark     --Pycelle           Eddard Stark     --Petyr Baelish     Eddard Stark     --Jon Snow         
+ ... omitted several edges

(Global) Network structure

Finally, it is often also informative to look at the overal characteristics of the network. We will do this in more detail enxt time, but just so you know:

The density of a measure represents the share of all connected to all possible connections in the network

edge_density(g)
[1] 0.1542857

Transistivity, also called the Clustering Cefficient indicates how much the network tends to be locally clustered. That is measured by the share of closed triplets. Again,w e will dig into that next time.

transitivity(g)

The diameter is the longest of teh shortest paths between two nodes of the network.

diameter(g, directed = F, weights = NA)
[1] 4

Finally, the mean distance, or average path lenght represents the mean of all shortest paths between all nodes. It is a measure of diffusion potential within a network.

mean_distance(g, directed = F)

Your turn

Ahh, you saw it comming, right? What about you explore the GoT network a bit on your own HERE. Lets see how that works out!

Directed Networks are comming…

So far so good, up to now we considered undirected networks, constructed by the amount characters co-occur. However, as you already might guess, that’s not where we stop. SOme general infos on directed networks:

An obvious example at the GoT case are family ties. Here, I will ose the nicely compiled dataset of the wonderful Shirin that can be found here. It contains a nodelist with house-affiliations and furtehr characteristics of main characters, and a edgelist of their family relationships.

Load the graph

rm(chars.main, g, g.danny, g.drogo, g.merge)
edges.fam <- readRDS("../data/GoT/union_edges.RDS")
nodes.fam <- readRDS("../data/GoT/union_characters.RDS")
head(nodes.fam)
head(edges.fam)

Lets construct teh graph. We now also feed in a set of nodes with their characteristics.

g <- graph_from_data_frame(edges.fam, 
                           vertices = nodes.fam,
                           directed = TRUE)
g
IGRAPH 813c92b DN-- 208 404 -- 
+ attr: name (v/c), male (v/n), culture (v/c), house (v/c), popularity (v/n), house2 (v/c), color (v/c),
| shape (v/c), type (e/c), color (e/c), lty (e/c)
+ edges from 813c92b (vertex names):
 [1] Lysa Arryn       ->Robert Arryn       Jasper Arryn     ->Alys Arryn        
 [3] Jasper Arryn     ->Jon Arryn          Jon Arryn        ->Robert Arryn      
 [5] Cersei Lannister ->Tommen Baratheon   Cersei Lannister ->Joffrey Baratheon 
 [7] Cassana Baratheon->Stannis Baratheon  Cersei Lannister ->Myrcella Baratheon
 [9] Selyse Florent   ->Shireen Baratheon  Cassana Baratheon->Renly Baratheon   
[11] Rhaelle Targaryen->Steffon Baratheon  Cassana Baratheon->Robert Baratheon  
[13] Robert Baratheon ->Tommen Baratheon   Robert Baratheon ->Joffrey Baratheon 
+ ... omitted several edges

Visualizing networks I

How does the plot look?

plot(g)

Well, thats some uninformative hairball. Such things often happen when we want to plot large networks. This is a good point to start using the parameters in the igraph plotting function. Next time I will introduce you to my current favorite, ggraph. However, the igraph plotting function is relatively easy to sue. so its worth (if only for the sake of illustration) to tweak through all the parameters to get THE GoT family graph, as pretty as possible.

For plotting the legend, I am summarizing the edge and node colors upfront. You will later see why.

color_vertices <- nodes.fam %>%
  group_by(house, color) %>%
  summarise(n = n()) %>%
  filter(!is.na(color))
colors_edges <- edges.fam %>%
  group_by(type, color) %>%
  summarise(n = n()) %>%
  filter(!is.na(color))

Ok, we are ready, lets do this plot!

plot(g,
     layout = layout_with_fr(g),
     vertex.label = gsub(" ", "\n", V(g)$name),
     vertex.shape = V(g)$shape,
     vertex.color = V(g)$color, 
     vertex.size = (V(g)$popularity + 0.5) * 5, 
     vertex.frame.color = "gray", 
     vertex.label.color = "black", 
     vertex.label.cex = 0.8,
     edge.arrow.size = 0.5,
     edge.color = E(g)$color,
     edge.lty = E(g)$lty)
legend("topleft", legend = c(NA, "Node color:", as.character(color_vertices$house), NA, "Edge color:", as.character(colors_edges$type)), pch = 10,
       col = c(NA, NA, color_vertices$color, NA, NA, colors_edges$color), pt.cex = 3, cex = 2, bty = "n", ncol = 1,
       title = "") 
legend("topleft", legend = "", cex = 3, bty = "n", ncol = 1,
       title = "Game of Thrones Family Ties")

What a beauty! Thanks to Shirin’s nice upfront work, it was rather easy to plot it that nicely. However, we could also define our colors as we wished. Here the R-Color Palettes might become handy.

Community Detection

You might have already guessed, we can very well also do a clustering exercise in networks. Here, we do not cluster nodes according to their similarity in attributes, but according to their connectivity. There are plenty of algorithms,, and we will explore further ones lateron. Most of them aim to find communities with maximum within/connectivity, and minimum between/connectivity.

However, most of them are not designed to work with directed networks. Therefore, we will convert our nice network for now to an undirected one.

g.ud <- as.undirected(g)

First, we will give it a try with the edge-betweenness algorithm (Newman-Girvan). Here, high-betweenness edges are removed sequentially (recalculating at each step) and the best partitioning of the network is selected.

Lets take a look how it works.

?cluster_edge_betweenness

And we now run it. As an hirarchical community detection technique. Since it is an hirarchical one, we can again plot a dendogram which we already know from the hirarchical clustering

ceb
IGRAPH clustering edge betweenness, groups: 12, mod: 0.84
+ groups:
  $`1`
   [1] "Alys Arryn"       "Elys Waynwood"    "Jasper Arryn"     "Jeyne Royce"      "Jon Arryn"       
   [6] "Lysa Arryn"       "Robert Arryn"     "Rowena Arryn"     "Edmure Tully"     "Sansa Stark"     
  [11] "Arya Stark"       "Bran Stark"       "Catelyn Stark"    "Eddard Stark"     "Jeyne Westerling"
  [16] "Rickon Stark"     "Robb Stark"       "Talisa Stark"     "Hoster Tully"     "Minisa Whent"    
  [21] "Petyr Baelish"   
  
  $`2`
   [1] "Cassana Baratheon"  "Cersei Lannister"   "Jaime Lannister"    "Joffrey Baratheon"  "Margaery Tyrell"   
   [6] "Myrcella Baratheon" "Renly Baratheon"    "Robert Baratheon"   "Selyse Florent"     "Shireen Baratheon" 
  + ... omitted several groups/vertices
plot(ceb, g.ud,
     vertex.frame.color = V(g)$color, # load the predefined color of the nodes (houses)
     vertex.size = (V(g)$popularity + 0.5) * 5 # define node-size by popularity) 
)

Lets only see how good it performs on the major houses, the rest is too small anyhow

bind_cols(com = ceb$membership, house = V(g.ud)$house) %>%
  group_by(house) %>%
  filter(n() >= 10) %>%
  ungroup() %>%
  table()
    house
com  House Baratheon House Frey House Greyjoy House Lannister House Martell House Stark House Targaryen House Tyrell
  1                0          0             0               0             0           7               0            0
  2                9          0             0               4             0           0               0            1
  3                1          0             0               0             2           0              13            0
  4                0         13             0               0             0           0               0            0
  5                0          7             0               9             0           0               0            0
  6                0          0            14               0             0           0               0            0
  7                0          0             0              13             0           0               0            0
  8                0          0             0               0            11           0               0            0
  9                0          0             0               0             0           6               0            0
  10               0          0             0               0             0          13               0            0
  11               0          0             0               0             0           0               0            9
  12               0          0             0               0             0           0               0            5

We see, indeed, that the communities for the most part capture the affiliation to the great houses.

Your turn

AGain, its time to have some fun on your own. HERE you will find another kaggle notebook where you can demonstrate your network analysis skills even more!

LS0tDQp0aXRsZTogJ00yLTEtMjogSW50cm9kdWN0aW9uIHRvIE5ldHdvcmsgQW5hbHlzaXMnDQphdXRob3I6ICJEYW5pZWwgUy4gSGFpbiAoZHNoQGJ1c2luZXNzLmFhdS5kaykiDQpkYXRlOiAiMDMvMTAvMjAxOCINCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDoNCiAgICBkZl9wcmludDogcGFnZWQNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KICBodG1sX25vdGVib29rOg0KICAgIGRmX3ByaW50OiBwYWdlZA0KICAgIG51bWJlcl9zZWN0aW9uczogbm8NCiAgICB0b2M6IHllcw0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0KIyMjIEdlbmVyaWMgcHJlYW1ibGUNClN5cy5zZXRlbnYoTEFORyA9ICJlbiIpDQoNCiMjIyBDbGVhbiBXb3Jrc3BhY2UgKEkgbGlrZSB0byBzdGFydCBjbGVhbikNCnJtKGxpc3Q9bHMoKSk7IGdyYXBoaWNzLm9mZigpICMgZ2V0IHJpZCBvZiBldmVyeXRoaW5nIGluIHRoZSB3b3Jrc3BhY2UNCmRldGFjaEFsbFBhY2thZ2VzIDwtIGZ1bmN0aW9uKCkgeyAjIEFsc28sIGRldGFjaCBwYWNrYWdlcyB0byBhdm9pZCBmdW5jdGlvbnMgbWFza2VkIGJ5IG90aGVycw0KICBiYXNpYy5wYWNrYWdlcyA8LSBjKCJwYWNrYWdlOnN0YXRzIiwicGFja2FnZTpncmFwaGljcyIsInBhY2thZ2U6Z3JEZXZpY2VzIiwicGFja2FnZTp1dGlscyIsInBhY2thZ2U6ZGF0YXNldHMiLCJwYWNrYWdlOm1ldGhvZHMiLCJwYWNrYWdlOmJhc2UiKQ0KICBwYWNrYWdlLmxpc3QgPC0gc2VhcmNoKClbaWZlbHNlKHVubGlzdChncmVnZXhwcigicGFja2FnZToiLHNlYXJjaCgpKSk9PTEsVFJVRSxGQUxTRSldDQogIHBhY2thZ2UubGlzdCA8LSBzZXRkaWZmKHBhY2thZ2UubGlzdCxiYXNpYy5wYWNrYWdlcykNCiAgaWYgKGxlbmd0aChwYWNrYWdlLmxpc3QpPjApICBmb3IgKHBhY2thZ2UgaW4gcGFja2FnZS5saXN0KSBkZXRhY2gocGFja2FnZSwgY2hhcmFjdGVyLm9ubHk9VFJVRSkNCn0NCmRldGFjaEFsbFBhY2thZ2VzKCk7IHJtKGRldGFjaEFsbFBhY2thZ2VzKQ0KDQojIyMgY2hlY2tpbmcgaWYgYWxsIHdlIG5lZWQgaXMgaW5zdGFsbGVkDQpsaXN0Lm9mLnBhY2thZ2VzIDwtIGMoImtuaXRyIiwgInRpZHl2ZXJzZSIsICJtYWdyaXR0ciIsICJkYXRhLnRhYmxlIiwgInNraW1yIikNCg0KbmV3LnBhY2thZ2VzIDwtIGxpc3Qub2YucGFja2FnZXNbIShsaXN0Lm9mLnBhY2thZ2VzICVpbiUgaW5zdGFsbGVkLnBhY2thZ2VzKClbLCJQYWNrYWdlIl0pXQ0KaWYobGVuZ3RoKG5ldy5wYWNrYWdlcykpIGluc3RhbGwucGFja2FnZXMobmV3LnBhY2thZ2VzKQ0Kcm0obGlzdC5vZi5wYWNrYWdlcywgbmV3LnBhY2thZ2VzKQ0KDQojIyMgTG9hZCBwYWNrYWdlcyAgU3RhbmRhcmQNCmxpYnJhcnkoa25pdHIpICMgRm9yIGRpc3BsYXkgb2YgdGhlIG1hcmtkb3duDQpsaWJyYXJ5KHRpZHl2ZXJzZSkgIyBDb2xsZWN0aW9uIG9mIGFsbCB0aGUgZ29vZCBzdHVmZiBsaWtlIGRwbHlyLCBnZ3Bsb3QyIGVjdC4NCmxpYnJhcnkobWFncml0dHIpICMgRm9yIGV4dHJhLXBpcGluZyBvcGVyYXRvcnMgKGVnLiAlPD4lKQ0KbGlicmFyeShkYXRhLnRhYmxlKSAjIEdvb2QgZm9ybWF0IHRvIHdvcmsgd2l0aCBsYXJnZSBkYXRhc2V0cw0KbGlicmFyeShza2ltcikgIyBOaWNlIGRlc2NyaXB0aXZlcw0KDQoNCiMjIyBLbml0ciBvcHRpb25zDQpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsDQogICAgICAgICAgICAgICBtZXNzYWdlID0gRkFMU0UsDQogICAgICAgICAgICAgICBmaWcuYWxpZ24gID0gImNlbnRlciINCiAgICAgICAgICAgICAgICkNCmBgYA0KDQpTb21lIGhvdXNla2VlcGluZyAoYWdhaW4pLCBpbnN0YWxsaW5nIG5lY2Vzc2FyeSBwYWNrYWdlcy4NCg0KYGBge3J9DQpsaXN0Lm9mLnBhY2thZ2VzIDwtIGMoImlncmFwaCIsICJ0aWR5Z3JhcGgiLCAiZ2dyYXBoIikNCg0KbmV3LnBhY2thZ2VzIDwtIGxpc3Qub2YucGFja2FnZXNbIShsaXN0Lm9mLnBhY2thZ2VzICVpbiUgaW5zdGFsbGVkLnBhY2thZ2VzKClbLCJQYWNrYWdlIl0pXQ0KaWYobGVuZ3RoKG5ldy5wYWNrYWdlcykpIGluc3RhbGwucGFja2FnZXMobmV3LnBhY2thZ2VzKQ0Kcm0obGlzdC5vZi5wYWNrYWdlcywgbmV3LnBhY2thZ2VzKQ0KYGBgDQoNCg0KIyBJbnRyb2R1Y3Rpb24NCg0KV2VsY29tZSB0byBNb2R1bGUgMi4gVGhpcyBzY3JpcHQgaXMgYXZhaWxhYmxlIGFzIFItbm90ZWJvb2sgKHByZXR0eSkgYXMgd2VsbCBhcyBleGVjdXRhYmxlIGp1cHl0ZXIgbm90ZWJvb2sgb24ga2FnZ2xlIFtoZXJlXShodHRwczovL2thZ2dsZS5jb20vZGFuaWVsaGFpbi9zZHMtMjAxOC1tMi0xLWludHJvLW53KS4gSEF2ZSBmdW4hDQoNCiMjIE5ldHdvcmtzLi4uIFNvIHdoYXQ/DQpTbywgYmVmb3JlIHdlIHRhbGsgYWJvdXQgbmV0d29ya3MsIG9uZSB0aGluZyB1cGZyb250Li4uIHdoeSBzaG91bGQgd2U/IEkgbWVhbiwgdGhleSB1bmRlbmlhYmx5IGxvb2sgcHJldHR5LCBkb24ndCB0aGV5Pw0KDQohW10oLi4vbWVkaWEvTTJfMV9uZXR3b3JrLnBuZyl7d2lkdGg9NzUwcHh9DQoNClNvbWVob3csIHRoZSB2aXN1YWxpemF0aW9uIG9mIG5ldHdvcmtzIGZhc2NpbmF0ZXMgdGhlIGh1bWFuIG1pbmQgKGZpbmQgYSBzaG9ydCBURUQgdGFsayBvbiBuZXR3b3JrcyBhbmQgaG93IHRoZXkgZGVwaWN0IG91ciB3b3JsZCBbaGVyZV0oaHR0cHM6Ly93d3cudGVkLmNvbS90YWxrcy9tYW51ZWxfbGltYV9hX3Zpc3VhbF9oaXN0b3J5X29mX2h1bWFuX2tub3dsZWRnZSkpLCBhbmQgaGFzIGV2ZW4gaW5zcGlyZWQgYW4gb3duIGFydCBtb3ZlbWVudCwgbmV0d29ya2lzbSAoc2VlIHNvbWUgZXhhbXBsZXMgW2hlcmVdKGh0dHBzOi8vd3d3LmJlaGFuY2UubmV0L2dhbGxlcnkvMTg0MDQ1L0xpbmtzKSkuIA0KDQpZZXQsIGJlc2lkZXMgdGhhdCwgaXMgdGhlcmUgYW4gYW5hbHl0aWNhbCB2YWx1ZSBmb3IgYSBkYXRhIHNjaWVudGlzdCB0byBib3RoZXIgYWJvdXQgbmV0d29ya3M/DQoNCiFbXSguLi9tZWRpYS9NMl8xX2dvb2dsZV9hcHBsZS5wbmcpe3dpZHRoPTc1MHB4fQ0KDQojIyBOZXR3b3JrcyBpbiBSDQpUaGVyZSBhcmUgYSBudW1iZXIgb2YgYXBwbGljYXRpb25zIGRlc2lnbmVkIGZvciBuZXR3b3JrIGFuYWx5c2lzIGFuZCB0aGUgY3JlYXRpb24gb2YgbmV0d29yayBncmFwaHMgc3VjaCBhcyBbZ2VwaGldKGh0dHBzOi8vZ2VwaGkub3JnKSBhbmQgW2N5dG9zY2FwZV0oaHR0cDovL2N5dG9zY2FwZS5vcmcpLiBUaG91Z2ggbm90IHNwZWNpZmljYWxseSBkZXNpZ25lZCBmb3IgaXQsIFIgaGFzIGRldmVsb3BlZCBpbnRvIGEgcG93ZXJmdWwgdG9vbCBmb3IgbmV0d29yayBhbmFseXNpcy4gDQoNClNpZ25pZmljYW50IG5ldHdvcmsgYW5hbHlzaXMgcGFja2FnZXMgZm9yIFIgaW5jbHVkZSB0aGUgW2BuZXR3b3JrYF0oaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL25ldHdvcmsvaW5kZXguaHRtbCksIFtgc25hYF0oaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL3NuYS9pbmRleC5odG1sKSwgYW5kIFtgaWdyYXBoYF0oaHR0cDovL2lncmFwaC5vcmcpIHBhY2thZ2UuIEluIGFkZGl0aW9uLCBbVGhvbWFzIExpbiBQZWRlcnNlbl0oaHR0cDovL3d3dy5kYXRhLWltYWdpbmlzdC5jb20pIGhhcyByZWNlbnRseSByZWxlYXNlZCB0aGUgW2B0aWR5Z3JhcGhgXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvdGlkeWdyYXBoL2luZGV4Lmh0bWwpIHBhY2thZ2UgdGhhdCBsZXZlcmFnZSB0aGUgcG93ZXIgb2YgYGlncmFwaGAgaW4gYSBtYW5uZXIgY29uc2lzdGVudCB3aXRoIHRoZSBbYHRpZHl2ZXJzZWBdKGh0dHA6Ly93d3cudGlkeXZlcnNlLm9yZykgd29ya2Zsb3cuIEV2ZW4gYmV0dGVyLCBoZSB0b3BzIGl0IHVwIHdpdGggW2BnZ3JhcGhgXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvZ2dyYXBoL2luZGV4Lmh0bWwpLCBhIGNvbnNpc3RlbnQgtGdncGxvdDK0LWxvb2stYW5kLWZlZWwgbmV0d29yayB2aXN1YWxpemF0aW9uIHBhY2thZ2UuDQoNClIgY2FuIGFsc28gYmUgdXNlZCB0byBtYWtlIGludGVyYWN0aXZlIG5ldHdvcmsgZ3JhcGhzIHdpdGggdGhlIFtodG1sd2lkZ2V0cyBmcmFtZXdvcmtdKGh0dHA6Ly93d3cuaHRtbHdpZGdldHMub3JnKSB0aGF0IHRyYW5zbGF0ZXMgUiBjb2RlIHRvIEphdmFTY3JpcHQuIENvb2wgaW1wbGVtZW50YXRpb25zIHRoZXJlb2YgYXJlIHRoZSBbYHZpek5ldHdvcmtgXShodHRwOi8vZGF0YXN0b3JtLW9wZW4uZ2l0aHViLmlvL3Zpc05ldHdvcmsvKSBhbmQgW2BuZXR3b3JrRDNgXShodHRwOi8vY2hyaXN0b3BoZXJnYW5kcnVkLmdpdGh1Yi5pby9uZXR3b3JrRDMvKSBwYWNrYWdlcy4NCg0KQXMgYW5hbHl0aWNhbCB0b29sLCBJIHdpbGwgaW4gdGhpcyBsYWIgbW9zdGx5IHVzZSBbYGlncmFwaGBdKGh0dHA6Ly9pZ3JhcGgub3JnKS4gSW4gdGVybXMgb2YgZnVuY3Rpb25zLCBpdCBpcyBwcmV0dHkgbXVjaCBlcXVpdmFsZW50IHRvIFtgbmV0d29ya2BdKGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9uZXR3b3JrL2luZGV4Lmh0bWwpLCB5ZXQgc2xpZ2h0bHkgbW9yZSBwb3dlcmZ1bCwgYmV0dGVyIGludGVncmF0ZWQsIGFuZCBtYWludGFpbmVkLiBTaW5jZSBib3RoIHBhY2thZ2VzIGhhdmUgbWFueSBvZiB0aGUgc2FtZSBmdW5jdGlvbnMsIGJldHRlciBkb24ndCBsb2FkIHRoZW0gYm90aCBhdCBvbmNlLg0KDQoNCiMjIFRoZSBCYXNpYyBTdHJ1Y3R1cmUgb2YgTmV0d29ya3MNCg0KIyMjIFRoZSBCYXNpYyBKYXJnb24NCkZpcnN0IG9mIGFsbCwgd2hhdCBpcyBhIG5ldHdvcms/IFBsYWlubHkgc3BlYWtpbmcsIGEgbmV0d29yayBpcyBhIHN5c3RlbSBvZiBlbGVtZW50cyB3aGljaCBhcmUgY29ubmVjdGVkIGJ5IHNvbWUgcmVsYXRpb25zaGlwLiBUaGUgdm9jYWJ1bGFyeSBjYW4gYmUgYSBiaXQgdGVjaG5pY2FsIGFuZCBldmVuIGluY29uc2lzdGVudCBiZXR3ZWVuIGRpZmZlcmVudCBkaXNjaXBsaW5lcywgcGFja2FnZXMsIGFuZCBzb2Z0d2FyZS4gVGhlIHdob2xlIHN5c3RlbSBpcyAoc3VycHJpc2UsIHN1cnByaXNlKSB1c3VhbGx5IGNhbGxlZCBhICoqbmV0d29yayoqIG9yICoqZ3JhcGgqKi4gVGhlIGVsZW1lbnRzIGFyZSBjb21tb25seSByZWZlcnJlZCB0byBhcyAqKm5vZGVzKiogKHN5c3RlbSB0aGVvcnkgamFyZ29uKSBvciAqKnZlcnRpY2VzKiogKGdyYXBoIHRoZW9yeSBqYXJnb24pIG9mIGEgZ3JhcGgsIHdoaWxlIHRoZSBjb25uZWN0aW9ucyBhcmUgKiplZGdlcyoqIG9yICoqbGlua3MqKi4gSSB3aWxsIG1vc3RseSByZWZlciB0byB0aGUgZWxlbWVudHMgYXMgbm9kZXMsIGFuZCB0aGVpciBjb25uZWN0aW9ucyBhcyBlZGdlcy4NCg0KIVtdKC4uL21lZGlhL00yXzFfbndfaWxsdS5wbmcpe3dpZHRoPTUwMHB4fQ0KDQpHZW5lcmFsbHksIG5ldHdvcmtzIGFyZSBhIGZvcm0gb2YgcmVwcmVzZW50aW5nICoqcmVsYXRpb25hbCBkYXRhKiouIFRoaXMgaXMgYSB2ZXJ5IGdlbmVyYWwgdG9vbCB0aGF0IGNhbiBiZSBhcHBsaWVkIHRvIG1hbnkgZGlmZmVyZW50IHR5cGVzIG9mIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiBhbGwga2luZCBvZiBlbGVtZW50cy4gVGhlIGNvbnRlbnQsIG1lYW5pbmcsIGFuZCBpbnRlcnByZXRhdGlvbiBmb3Igc3VyZSBkZXBlbmRzIG9uIHdoYXQgZWxlbWVudHMgd2UgZGlzcGxheSwgYW5kIHdoaWNoIHR5cGVzIG9mIHJlbGF0aW9uc2hpcHMuIEZvciBleGFtcGxlOg0KDQoNCiogSW4gU29jaWFsIE5ldHdvcmsgQW5hbHlzaXM6DQogICAgICogTm9kZXMgcmVwcmVzZW50IGFjdG9ycyAod2hpY2ggY2FuIGJlIHBlcnNvbnMsIGZpcm1zIGFuZCBvdGhlciBzb2NpYWxseSBjb25zdHJ1Y3RlZCBlbnRpdGllcykNCiAgICAgKiBFZGdlcyByZXByZXNlbnQgcmVsYXRpb25zaGlwcyBiZXR3ZWVuIHRoaXMgYWN0b3JzIChmcmllbmRzaGlwLCBpbnRlcmFjdGlvbiwgY28tYWZmaWxpYXRpb24sIHNpbWlsYXJpdHkgZWN0LikNCiogT3RoZXIgdHlwZXMgb2YgbmV0d29yaw0KICAgICAqIENoZW1pc3RyeTogSW50ZXJhY3Rpb24gYmV0d2VlbiBtb2xlY3VsZXMNCiAgICAgKiBDb21wdXRlciBTY2llbmNlOiBUaGUgd2lybGQtd2lkZS13ZWIsIGludGVyLSBhbmQgaW50cmFuZXQgdG9wb2xvZ2llcw0KICAgICAqIEJpb2xvZ3k6IEZvb2Qtd2ViLCBhbnQtaGl2ZXMNCg0KVGhlIHBvc3NpYmlsaXRpZXMgdG8gZGVwaWN0IHJlbGF0aW9uYWwgZGF0YSBhcmUgbWFuaWZvbGQuIEZvciBleGFtcGxlOg0KDQoqIFJlbGF0aW9ucyBhbW9uZyBwZXJzb25zDQogICAgICogS2luc2hpcDogbW90aGVyIG9mLCB3aWZlIG9mLi4uDQogICAgICogT3RoZXIgcm9sZSBiYXNlZDogYm9zcyBvZiwgc3VwZXJ2aXNvciBvZi4uLg0KICAgICAqIENvZ25pdGl2ZS9wZXJjZXB0dWFsOiBrbm93cywgYXdhcmUgb2Ygd2hhdCB0aGV5IGtub3cuLi4NCiAgICAgKiBBZmZlY3RpdmU6IGxpa2VzLCB0cnVzdHMuLi4NCiAgICAgKiBJbnRlcmFjdGlvbjogZ2l2ZSBhZHZpY2UsIHRhbGtzIHRvLi4uDQogICAgICogQWZmaWxpYXRpb246IGJlbG9uZyB0byBzYW1lIGNsdWJzLCBzaGFyZXMgc2FtZSBpbnRlcmVzdHMuLi4NCiogUmVsYXRpb25zIGFtb25nIG9yZ2FuaXphdGlvbnMNCiAgICAgKiBBcyBjb3Jwb3JhdGUgZW50aXRpZXMNCiAgICAgKiBCdXkgZnJvbSAvIHNlbGwgdG8sIGxlYXNlcyB0bywgb3V0c291cmNlcyB0bw0KICAgICAqIE93bnMgc2hhcmVzIG9mLCBzdWJzaWRpYXJ5IG9mDQogICAgICogSm9pbnQgdmVudHVyZXMsIHN0cmF0ZWdpYyBhbGxpYW5jZXMNCiAgICAgKiBWaWEgdGhlaXIgbWVtYmVycw0KICAgICAgICAgICogUGVyc29ubmVsIGZsb3dzDQogICAgICAgICAgKiBJbnRlcmxvY2tpbmcgZGlyZWN0b3JhdGVzDQogICAgICAgICAgKiBQZXJzb25hbCBmcmllbmRzaGlwcw0KICAgICAgICAgICogQ28tbWVtYmVyc2hpcHMNCiogUmVsYXRpb25zIG90aGVyIChub24tc29jaWFsKSBlbnRpdGllcw0KICAgICAqIFBhdGVudHMNCiAgICAgICAgICAqIFBhdGVudHMgY2l0aW5nIG90aGVyIHBhdGVudHMNCiAgICAgICAgICAqIENvLW9jY3VycmVuY2Ugb2YgdGVjaG5vbG9naWNhbCBjbGFzc2VzDQogICAgICpSZXNlYXJjaCBmaWVsZHMNCiAgICAgICAgICAqIHRocm91Z2ggY2l0YXRpb25zDQogICAgICAgICAgKiB0aHJvdWdoIHBlb3BsZSBjby1hZmZpbGlhdGVkIHdpdGggZmllbGRzDQogICAgICpTZWN0b3JzDQogICAgICAgICAgKiBpbnB1dC1vdXRwdXQgcmVsYXRpb25zDQogICAgICAgICAgKiBMYWJvciBtb2JpbGl0eQ0KICAgICAqVGVjaG5vbG9naWVzDQogICAgICAgICAgKiBQYXRlbnQgSVBDIGNsYXNzZXMNCiAgICAgICAgICAqIFNlbWFudGljIGNvLW9jY3VycmVuY2UgDQoNCg0KKipOb3RlOiBDb250ZW50IG1hdHRlcnMhKiogRWFjaCByZWxhdGlvbiB5aWVsZHMgYSBkaWZmZXJlbnQgc3RydWN0dXJlICYgaGFzIGRpZmZlcmVudCBlZmZlY3RzLiBUaGVvcmllcyBtaWdodCBtYWtlIHNlbnNlIG9uIGludGVyLXBlcnNvbmFsLCBidXQgbm90IGludGVyLW9yZ2FuaXphdGlvbmFsIG9yIG5vbi1zb2NpYWwgY29udGV4dC4NCg0KDQojIyMgVGhlIERhdGEtU3RydWN0dXJlIG9mIFJlbGF0aW9uYWwgRGF0YQ0KDQojIyMjIEVkZ2VsaXN0DQpNT3N0IHJlYWwgd29ybGQgcmVsYXRpb25hbCBkYXRhIGlzIHRvIGJlIGZvdW5kIGluIHdoYXQgd2UgY2FsbCBhbiAqKmVkZ2UgbGlzdCoqLCBhIGRhdGFmcmFtZSB0aGF0IGNvbnRhaW5zIGEgbWluaW11bSBvZiB0d28gY29sdW1ucywgb25lIGNvbHVtbiBvZiAqbm9kZXMqIHRoYXQgYXJlIHRoZSBzb3VyY2Ugb2YgYSBjb25uZWN0aW9uIGFuZCBhbm90aGVyIGNvbHVtbiBvZiBub2RlcyB0aGF0IGFyZSB0aGUgdGFyZ2V0IG9mIHRoZSBjb25uZWN0aW9uLiBUaGUgbm9kZXMgaW4gdGhlIGRhdGEgYXJlIGlkZW50aWZpZWQgYnkgdW5pcXVlIElEcy4gSWYgdGhlIGRpc3RpbmN0aW9uIGJldHdlZW4gc291cmNlIGFuZCB0YXJnZXQgaXMgbWVhbmluZ2Z1bCwgdGhlIG5ldHdvcmsgaXMgKipkaXJlY3RlZCoqLiBJZiB0aGUgZGlzdGluY3Rpb24gaXMgbm90IG1lYW5pbmdmdWwsIHRoZSBuZXR3b3JrIGlzICoqdW5kaXJlY3RlZCoqIChtb3JlIG9uIHRoYXQgbGF0ZXIpLiBTbywgZXZlcnkgcm93IHRoYXQgY29udGFpbnMgdGhlIElEIG9mIG9uZSBlbGVtZW50IGluIGNvbHVtbiAxLCBhbmQgdGhlIElEIG9mIGFub3RoZXIgZWxlbWVudCBpbiBjb2x1bW4gMiBpbmRpY2F0ZXMgdGhhdCBhIGNvbm5lY3Rpb24gYmV0d2VlbiB0aGVtIGV4aXN0cy4gQW4gZWRnZSBsaXN0IGNhbiBhbHNvIGNvbnRhaW4gYWRkaXRpb25hbCBjb2x1bW5zIHRoYXQgZGVzY3JpYmUgKiphdHRyaWJ1dGVzKiogb2YgdGhlIGVkZ2VzIHN1Y2ggYXMgYSBtYWduaXR1ZGUgYXNwZWN0IGZvciBhbiBlZGdlLiBJZiB0aGUgZWRnZXMgaGF2ZSBhIG1hZ25pdHVkZSBhdHRyaWJ1dGUgdGhlIGdyYXBoIGlzIGNvbnNpZGVyZWQgKip3ZWlnaHRlZCoqIChtb3JlIG9uIHRoYXQgbGF0ZXIpLiBCZWxvdyBhbiBleGFtcGxlIG9mYSBtaW5pbWFsIGVkZ2UgbGlzdCBjcmVhdGVkIHdpdGggdGhlIGB0aWJibGUoKWAgZnVuY3Rpb24uDQoNCmBgYHtyIGVkZ2VsaXN0c30NCmVkZ2VfbGlzdCA8LSB0aWJibGUoZnJvbSA9IGMoMSwgMiwgMiwgMywgNCksIHRvID0gYygyLCAzLCA0LCAyLCAxKSkNCmVkZ2VfbGlzdA0KYGBgDQoNClNvbWV0aW1lcyBpdCBpcyBwcmVmZXJhYmxlIHRvIGFsc28gY3JlYXRlIGEgc2VwYXJhdGUgbm9kZSBsaXN0LiBBdCBpdHMgc2ltcGxlc3QsIGEgKipub2RlIGxpc3QqKiBpcyBhIGRhdGEgZnJhbWUgd2l0aCBhIHNpbmdsZSBjb2x1bW4gLSB3aGljaCBJIHdpbGwgbGFiZWwgYXMgImlkIiAtIHRoYXQgbGlzdHMgdGhlIG5vZGUgSURzIGZvdW5kIGluIHRoZSBlZGdlIGxpc3QuIFRoZSBhZHZhbnRhZ2Ugb2YgY3JlYXRpbmcgYSBzZXBhcmF0ZSBub2RlIGxpc3QgaXMgdGhlIGFiaWxpdHkgdG8gYWRkIGF0dHJpYnV0ZSBjb2x1bW5zIHRvIHRoZSBkYXRhIGZyYW1lIHN1Y2ggYXMgdGhlIG5hbWVzIG9mIHRoZSBub2RlcyBvciBhbnkga2luZCBvZiBncm91cGluZ3MuDQoNCmBgYHtyIG5vZGVsaXN0c30NCmxpYnJhcnkodGlkeXZlcnNlKQ0Kbm9kZV9saXN0IDwtIHRpYmJsZShpZCA9IDE6NCwgZ3JvdXAgPSBzYW1wbGUobGV0dGVyc1sxOjJdLCA0LCByZXBsYWNlID0gVFJVRSkpDQpub2RlX2xpc3QNCmBgYA0KDQojIyMjIEFkamFjZW5jeSBNYXRyaXgNCg0KQSBzZWNvbmQgcG9wdWxhciBmb3JtIG9mIG5ldHdvcmsgcmVwcmVzZW50YXRpb24gaXMgdGhlICoqYWRqYWNlbmN5LW1hdHJpeCoqIChhbHNvIGNhbGxlZCAqKnNvY2lvLW1hdHJpeCoqKS4gSXQgaXMgcmVwcmVzZW50ZWQgYXMgYSAkbipuJCBtYXRyaXgsIHdoZXJlICRuJCBzdGFuZHMgZm9yIHRoZSBudW1iZXIgb2YgZWxlbWVudHMgb2Ygd2hpY2ggdGhlaXIgcmVsYXRpb25zaGlwcyBzaG91bGQgYmUgcmVwcmVzZW50ZWQuIFRoZSB2YWx1ZSBpbiB0aGUgY2VsbCB0aGF0IGludGVyY2VwdHMgcm93ICRuJCBhbmQgY29sdW1uICRtJCBpbmRpY2F0ZXMgaWYgYW4gZWRnZSBpcyBwcmVzZW50ICg9MSkgb3IgYWJzZW50ICg9MCkuDQoNClRpcDogR2l2ZW4gYW4gZWRnZWxpc3QsIGFuIGFkamFjZW5jeSBtYXRyaXggY2FuIGVhc2lseSBiZSBwcm9kdWNlZCBieSBjcm9zc3RhYnVsYXRpbmc6DQoNCmBgYHtyIG1hdHJpeH0NCmFkal9tYXRyaXggPC0gdGFibGUoZWRnZV9saXN0KSAlPiUgYXMubWF0cml4KCkNCmFkal9tYXRyaXgNCmBgYA0KDQojIyMjIEdlbmVyYXRpbmcgYSBHcmFwaCBPYmplY3QgaW4gYGlncmFwaGANCg0KVG8gY3JlYXRlIGFuIGBpZ3JhcGhgIG9iamVjdCBmcm9tIGFuIGVkZ2UtbGlzdCBkYXRhIGZyYW1lIHdlIGNhbiB1c2UgdGhlIGBncmFwaF9mcm9tX2RhdGFfZnJhbWUoKWAgZnVuY3Rpb24sIHdoaWNoIGlzIGEgYml0IG1vcmUgc3RyYWlnaHQgZm9yd2FyZCB0aGFuIGBuZXR3b3JrKClgLiBUaGVyZSBhcmUgdGhyZWUgYXJndW1lbnRzIGluIHRoZSBgZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKClgIGZ1bmN0aW9uOiBkLCB2ZXJ0aWNlcywgYW5kIGRpcmVjdGVkLiBIZXJlLCBkIHJlZmVycyB0byB0aGUgZWRnZSBsaXN0LCB2ZXJ0aWNlcyB0byB0aGUgbm9kZSBsaXN0LCBhbmQgZGlyZWN0ZWQgY2FuIGJlIGVpdGhlciBgVFJVRWAgb3IgYEZBTFNFYCBkZXBlbmRpbmcgb24gd2hldGhlciB0aGUgZGF0YSBpcyBkaXJlY3RlZCBvciB1bmRpcmVjdGVkLiBCeSBkZWZhdWx0LCBgZ3JhcGguZGF0YS5mcmFtZSgpYCB0cmVhdHMgdGhlIGZpcnN0IHR3byBjb2x1bW5zIG9mIHRoZSBlZGdlIGxpc3QgYW5kIGFueSByZW1haW5pbmcgY29sdW1ucyBhcyBlZGdlIGF0dHJpYnV0ZXMuDQoNCmBgYHtyIGlncmFwaCBvYmplY3R9DQpsaWJyYXJ5KGlncmFwaCkNCmcgPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGQgPSBlZGdlX2xpc3QsIHZlcnRpY2VzID0gbm9kZV9saXN0LCBkaXJlY3RlZCA9IEZBTFNFKQ0KZw0KYGBgDQoNCkxldHMgaW5zcGVjdCB0aGUgcmVzdWx0aW5nIG9iamVjdC4gQW4gYGlncmFwaGAgZ3JhcGggb2JqZWN0IHN1bW1hcnkgcmV2ZWFscyBzb21lIGludGVyZXN0aW5nIGluZm9ybWF0aW9ucy4NCg0KKiBGaXJzdCwgaXQgdGVsbHMgdXMgdGhlIGdyYXBoLXR5cGU6IHVuZGlyZWN0ZWQgYFVOYCwgb3IgIGRpcmVjdGVkIGBETmANCiogQWZ0ZXJ3YXJkcywgdGhlIG51bWJlciBvZiBub2RlcyAoNCksIGFuZCBlZGdlcyAoNikNCiogRm9sbG93ZWQgYnkgdGhlIG5vZGUgYXR0cmlidXRlcyAobm9kZSBsZXZlbCB2YXJpYWJsZXMpLCB3aGljaCBpbiB0aGlzIGNhc2UgYXJlIG9ubHkgdGhlaXIgbmFtZSAoYGF0dHI6IG5hbWUgKHYvYylgKQ0KKiBMYXN0bHksIGEgbGlzdCBvZiBhbGwgZXhpc3RpbmcgZWRnZXMuIE5vdGU6IGBuLS1tYCBpbmRpY2F0ZXMgYW4gdW5kaXJlY3RlZCwgYG4tPm1gIGFuIGRpcmVjdGVkIGVkZ2UuDQoNCkxldHMgdGFrZSBhIGxvb2sgYXQgdGhlIHN0cnVjdHVyZSBvZiB0aGUgb2JqZWN0Og0KDQpgYGB7cn0NCmdsaW1wc2UoZ1tbMV1dKQ0KYGBgDQoNCldlIHNlZSwgdGhlIG9iamVjdCBoYXMgYSBsaXN0LWZvcm1hdCwgY29uc2lzdGluZyBvZiBzZXBwZXJhdGUgbGlzdHMgZm9yIGV2ZXJ5IG5vZGUsIGNvbnRhaW5pbmcgc29tZSBhdHRyaWJ1dGVzIHdoaWNoIGFyZSBpcnJlbGV2YW50IG5vdywgYW5kIGFuIGVkZ2VsaXN0IGZvciBldmVyeSBub2RlLCBjYXB0dXJpbmcgaXRzIGVnby1uZXR3b3JrIChlZy4sIGAuLiAuLi0gYXR0cigqLCAibmFtZXMiKT0gY2hyIFsxOjJdICIyIiAiNCJgKQ0KDQpXZSBjYW4gYWxzbyBwbG90IGl0IHRvIHRha2UgYSBsb29rLiBgaWdyYXBoYCBvYmplY3QgY2FuIGJlIGRpcmVjdGx5IHVzZWQgd2l0aCB0aGUgYHBsb3QoKWAgZnVuY3Rpb24uIFRoZSByZXN1bHRzIGNhbiBiZSBhZGp1c3RlZCB3aXRoIGEgc2V0IG9mIHBhcmFtZXRlcnMgd2Ugd2lsbCBkaXNjb3ZlciBsYXRlci4gSXQncyBub3Qgc3VwZXIgcHJldHR5LCB0aGVyZWZvcmUgd2Ugd2lsbCBsYXRlciBhbHNvIGV4cGxvcmUgbW9yZSBwb3dlcmZ1bGwgcGxvdHRpbmcgdG9vbHMgZm9yIHJnYXBocy4gSG93ZXZlciwgaXRzIHF1aWNrJmRpcnR5LCBzbyBsZXRzIHRha2UgaXQgbGlrZSB0aGF0IGZvciBub3cuDQoNCmBgYHtyfQ0KcGxvdChnKQ0KYGBgDQoNClllYWgsIHRoYXQncyB0aGUgZ3JhcGguIFdlICBXZSBjYW4gYWxzbyB1c2UgdGhlIGFkamFjZW5jeSBtYXRyaXggdG8gY3JlYXRlIHRoZSBzYW1lIGdyYXBoLg0KDQoNCmBgYHtyfQ0KZyA8LSBncmFwaF9mcm9tX2FkamFjZW5jeV9tYXRyaXgoYWRqX21hdHJpeCwgbW9kZSA9ICJ1bmRpcmVjdGVkIikNCmcNCmBgYA0KDQpXZSBjYW4gaW5zcGVjdCBhbmQgbWFuaXB1bGF0ZSB0aGUgbm9kZXMgdmlhIGBWKGcpYCAoViBmb3IgdmVydGljZXMsIGl0cyBncmFwaC10aGVvcnkgc2xhbmcpLCBhbmQgZWRnZXMgd2l0aCBgRShnKWANCg0KYGBge3J9DQpWKGcpDQpFKGcpDQpgYGANCg0KV2UgY2FuIGFsc28gdXNlIG1vc3Qgb2YgdGhlIGJhc2UtUiBzbGljaW5nJmRpY2luZy4NCg0KYGBge3J9DQpWKGcpWzE6M10NCkUoZylbMjo0XQ0KYGBgDQoNClJlbWVtYmVyLCBpdCdzIGEgbGlzdC1vYmplY3QuIFNvLCBpZiB3ZSBqdXN0IHdhbnQgdG8gaGF2ZSB0aGUgdmFsdWVzLCB3ZSBoYXZlIHRvIHVzZSB0aGUgZG91YmxlIGJyYWNrZXQgYFtbeF1dYC4gDQoNCmBgYHtyfQ0KVihnKVtbMTozXV0NCmBgYA0KDQpXZSBjYW4gYWxzbyB1c2UgdGhlIGAkYCBub3RhdGlvbi4NCg0KYGBge3J9DQpWKGcpJG5hbWUNCmBgYA0KDQojIE5ldHdvcmtzIGFyZSBjb21pbmcuLi4NCg0KIVtdKC4uL21lZGlhL00yXzFfZ290LmpwZyl7d2lkdGg9NTAwcHh9DQoNClNvLCBsZXRzIGdldCBzZXJpb3VzLiBBcHByb3ByaWF0ZSBmb3IgdGhlIHdlYXRoZXIgdGhlc2UgZGF5cyBpbiBEZW5tYXJrLCB0aGUgdGhlbWUgaXMgIndpbnRlciBpcyBjb21taW5nLi4uIi4gVGhlcmVmb3JlLCB3ZSB3aWxsIGhhdmUgc29tZSBmdW4gYW5hbHlzaW5nIHRoZSBHYW1lIG9mIFRocm9uZXMgZGF0YSBwcm92aWRlZCBieSBbQW5kcmV3IEJldmVyaWRnZV0oaHR0cHM6Ly9naXRodWIuY29tL21hdGhiZXZlcmlkZ2UvYXNvaWFmKS4gSXQgaXMgYSBDaGFyYWN0ZXIgSW50ZXJhY3Rpb24gTmV0d29ya3MgZm9yIEdlb3JnZSBSLiBSLiBNYXJ0aW4ncyAiQSBTb25nIG9mIEljZSBhbmQgRmlyZSIgc2FnYSAoeWVzLCB3ZSBhcmUgdGFsa2luZyBhYm91dCB0aGUgYm9va3MuLi4pLiBUaGVzZSBuZXR3b3JrcyB3ZXJlIGNyZWF0ZWQgYnkgY29ubmVjdGluZyB0d28gY2hhcmFjdGVycyB3aGVuZXZlciB0aGVpciBuYW1lcyAob3Igbmlja25hbWVzKSBhcHBlYXJlZCB3aXRoaW4gMTUgd29yZHMgb2Ygb25lIGFub3RoZXIgaW4gb25lIG9mIHRoZSBib29rcyBpbiAiQSBTb25nIG9mIEljZSBhbmQgRmlyZS4iIFRoZSBlZGdlIHdlaWdodCBjb3JyZXNwb25kcyB0byB0aGUgbnVtYmVyIG9mIGludGVyYWN0aW9ucy4gVEhpcyBpcyBhIG5pY2Ugc2tpbGwgeW91IHdpbGwgaGF2ZSBhZmV0ZXIgdGhlIHNlY29uZCBwYXJ0IG9mIE0yIG9uIHlvdXIgb3duLg0KDQojIyBCdWlsZCB0aGUgZ3JhcGgNCg0KDQpgYGB7cn0NCmVkZ2VzLmNvb2MuYWxsIDwtIGZyZWFkKCIuLi9pbnB1dC9Hb1QvYXNvaWFmLWFsbC1lZGdlcy5jc3YiLCBkYXRhLnRhYmxlID0gRkFMU0UpIA0Kbm9kZXMuY29vYy5hbGwgPC0gZnJlYWQoIi4uL2lucHV0L0dvVC9hc29pYWYtYWxsLW5vZGVzLmNzdiIsIGRhdGEudGFibGUgPSBGQUxTRSkgDQpoZWFkKGVkZ2VzLmNvb2MuYWxsKQ0KYGBgDQoNClNvLCB0aGF0J3Mgd2hhdCB3ZSBoYXZlLCBhIGNsYXNzaWNhbCBlZGdlbGlzdCwgd2l0aCBpZDEgaW4gY29sdW1uIDEgYW5kIGlkMiBpbiBjb2x1bW4yLiBOb3RlLCB0aGUgZWRnZXMgYXJlIGluIHRoaXMgY2FzZSB3ZWlnaHRlZC5JIGRvbid0IGxpa2UgdGhlIHNlcHBlcmF0aW5nICItIiBiZXR3ZWVuIGluIHRoZSBuYW1lcywgbGV0cyBnZXQgcmlkIG9mIHRoZW0uIA0KDQpgYGB7cn0NCmNvbG5hbWVzKGVkZ2VzLmNvb2MuYWxsKSA8LSB0b2xvd2VyKGNvbG5hbWVzKGVkZ2VzLmNvb2MuYWxsKSkNCmVkZ2VzLmNvb2MuYWxsICU8PiUNCiAgbXV0YXRlKHNvdXJjZSA9IGdzdWIoIi0iLCAiICIsIHNvdXJjZSksDQogICAgICAgICB0YXJnZXQgPSBnc3ViKCItIiwgIiAiLCB0YXJnZXQpKSANCmBgYA0KDQpPaywgbGV0cyBzZWUgaG93IG1hbnkgY2hhcmFjdGVycyB3ZSBoYXZlIG92ZXJhbC4NCg0KYGBge3J9DQplZGdlcy5jb29jLmFsbCAlPiUNCiAgc2VsZWN0KC10eXBlKSAlPiUNCiAgZ2F0aGVyKHgsIG5hbWUsIHNvdXJjZTp0YXJnZXQpICU+JSANCiAgbl9kaXN0aW5jdCguJG5hbWUpDQpgYGANCg0KVGhhdCdzIGEgbG90LiBXZSBtaWdodCB3YW50IHRvIHJlc3RyaWN0IG91cnNlbGZlcyBmaXJzdCB0byBhIHNtYWxsIHNldCBvZiB0aGUgNTAgbW9zdCBjb25uZWN0ZWQgbm9kZXMuDQoNCmBgYHtyfQ0KY2hhcnMubWFpbiA8LSBlZGdlcy5jb29jLmFsbCAlPiUNCiAgc2VsZWN0KC10eXBlKSAlPiUNCiAgZ2F0aGVyKHgsIG5hbWUsIHNvdXJjZTp0YXJnZXQpICU+JQ0KICBncm91cF9ieShuYW1lKSAlPiUNCiAgc3VtbWFyaXNlKHN1bV93ZWlnaHQgPSBzdW0od2VpZ2h0KSkgJT4lDQogIHVuZ3JvdXAoKSAlPiUNCiAgYXJyYW5nZShkZXNjKHN1bV93ZWlnaHQpKSAlPiUNCiAgdG9wX24oNTApDQoNCmhlYWQoY2hhcnMubWFpbikNCmBgYA0KDQpTbyBmYXIgc28gZ29vZCwgaWYgd2Ugb25seSBnbyBieSBlZGdlIHdlaWdodHMsIFNlZW1zIGFzIGlmIFR5cmlvbiBtaWdodCBtYWtlIGl0Li4uLiBteSBmYXZvcml0ZSBhbnlob3cuIExldHMgcmVkdWNlIG91ciBlZGdlbGlzdCB0byB0aGlzIG1haW4gY2hhcmFjdGVycywganVzdCB0byB3YXJtIHVwIGFuZCBrZWVwIHRoZSBvdmVydmlldy4NCg0KYGBge3J9DQplZGdlcy5jb29jIDwtIGVkZ2VzLmNvb2MuYWxsICU+JQ0KICBmaWx0ZXIoc291cmNlICVpbiUgY2hhcnMubWFpbiRuYW1lICYgdGFyZ2V0ICVpbiUgY2hhcnMubWFpbiRuYW1lKSAlPiUNCiAgc2VsZWN0KHNvdXJjZSwgdGFyZ2V0LCB3ZWlnaHQpDQpgYGANCg0KDQpgYGB7cn0NCmcgPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGQgPSBlZGdlcy5jb29jLCBkaXJlY3RlZCA9IEZBTFNFKQ0KZw0KYGBgDQoNCk5vdGUgdGhhdCB0aGlzIGNvLW9jY3VyZW5jZSBuZXR3b3JrIGlzIHdlaWdodGVkIChudW1iZXIgb2YgY28tb2NjdXJlbmNlKSwgYW5kIHVuZGlyZWN0ZWQuDQoNCmBgYHtyfQ0KaXNfd2VpZ2h0ZWQoZykNCmlzX2RpcmVjdGVkKGcpDQpgYGANCg0KIyMgSW5zcGVjdCB0aGUgZ3JhcGgNCg0KIyMjIE92ZXJhbCBncmFwaCBhdHRyaWJ1dGVzDQoNCldlIGFscmVhZHkga25vdyBmcm9tIHRoZSBzdW1tYXJ5LCBidXQgd2UgY2FuIGFsc28gY291bnQgdGhlIG51bWJlciBvZiBub2RlcyBhbmQgZWRnZXMgYXMgZm9sbG93czoNCg0KYGBge3J9DQojIENvdW50IG51bWJlciBvZiBlZGdlcw0KZ3NpemUoZykNCg0KIyBDb3VudCBudW1iZXIgb2YgdmVydGljZXMNCmdvcmRlcihnKQ0KYGBgDQoNCldlIGNhbiBnaXZlIHRoZSBncmFwaCBhIGZpcnN0IHBsb3QgdG8gc2VlIHdoYXQgaGFwcGVucyB0aGVyZS4gSXQncyBub3QgcHJldHR5LCBidXQgd2Ugd2lsbCBmaW5lLXR1bmUgaXQgbGF0ZXIuDQoNCmBgYHtyfQ0KcGxvdChnLA0KICAgICBlZGdlLndpZHRoID0gKEUoZykkd2VpZ2h0IC8gbWF4KEUoZykkd2VpZ2h0KSkgKiA1ICAjIE9ubHkgYXJndW1lbnQgd2UgdXNlIHNvIGZhciBmb3IgdGhlIHdlaWdodGVkIGVkZ2VzDQogICAgICkNCmBgYA0KDQpJUyByZWFsbHkgbm90IHByZXR0eS4gQnV0IHdlIHdpbGwgd29yayBvbiB0aGF0IGxhdGVyLiBIb3dldmVyLCB3ZSBhbHJlYWR5IHNlZSB0aGF0IHNvbWUgbm9kZXMgYXJlIG5vdCBjb25uZWN0ZWQgKGlzb2xhdGVkKSwgc28gbGV0cyBkcm9wIHRoZW0gZm9yIG91ciBuZXR3b3JrIGFuYWx5c2lzLiBMZXRzIGFsc28gZ2V0IHJpZCBvZiBlZGdlcyB3aXRoIHN1cGVyIHNtYWxsIHdlaWdodC4NCg0KYGBge3J9DQpnIDwtIGRlbGV0ZV9lZGdlcyhnLCBFKGcpW3dlaWdodCA8IDIwXSkgIyBIb3cgdG8gZGVsZXRlIGVkZ2VzIGluIGEgZ3JhcGggcGJqZWN0DQpnIDwtIGRlbGV0ZV92ZXJ0aWNlcyhnLCBkZWdyZWUoZykgPT0gMCkgIyBIb3cgdG8gZGVsZXRlIG5vZGVzIGluIGEgZ3JhcGggcGJqZWN0DQpgYGANCg0KIyMjIEVkZ2VzDQoNCkxldHMgc2VlIGEgYml0IHdoaWNoIG9wdGlvbnMgd2UgaGF2ZSB0byBzZWxlY3QgZWRnZXMuIFdlIGNvdWxkIGZvciBleGFtcGxlIHVzZSBgaW5jKClgIHRvIHNlbGVjdCBvbmx5IGVkZ2VzIHRoYXQgaW5jbHVkZSBhIGNlcnRhaW4gbm9kZS4NCg0KKipOb3RlOioqIEFsbW9zdCBhbGwgZWRnZSBhbmQgbWFueSBmdXJ0ZWhyIGdyYXBoIGZ1bmN0aW9ucyB0byBmb2xsb3csIGhhdmUgYW4gYXJndW1lbnQgY2FsbGVkIGBtb2RlYC4gSGVyZSwgaXQgZG9lc24ndCBtYXR0ZXIsIHNpbmNlIHdlIGFodmUgYW4gdW5kaXJlY3RlZCBuZXR3b3JrLiBJbiBjYXNlIHRoZSBlZGdlcyBhcmUgZGlyZWN0ZWQsIHdlIHdhbnQgdG8gc3BlY2lmeSB3aGljaCBtb2RlIHRvIGNvbnNpZGVyIChgbW9kZSA9IGMoImFsbCIsICJvdXQiLCAiaW4iLCAidG90YWwiKWApLiBNb3JlIG9uIHRoYXQgYXQgYSBsYXRlciBwb2ludC4NCg0KYGBge3J9DQpFKGcpW1tpbmMoIkRhZW5lcnlzIFRhcmdhcnllbiIpXV0gIA0KYGBgDQoNCldlIGNvdWxkIGFsc28gc2VsZWN0IHRoZW0gZHVlIHRvIHRoZWlyIGNoYXJhY3RlcmlzdGljcw0KDQpgYGB7cn0NCkUoZylbW3dlaWdodCA+PSAxNTBdXQ0KYGBgDQoNCk9yIHBsb3QgdGhlaXIgd2VpZ2h0IGRpc3RyaWJ1dGlvbg0KDQpgYGB7cn0NCmhpc3QoRShnKSR3ZWlnaHQpDQpgYGANCg0KVGhlcmUgaXMgbXVjaGcgbW9yZSwgYnV0IGxldHMgbGVhdmUgaXQgd2l0aCB0aGF0IGZvciBub3cuDQoNCiMjIyBOb2Rlcw0KDQpUaGUgbm9kZSBsZXZlbCBnaXZlcyB1cyB0aGUgb3Bwb3J0dW5pdHkgdG8gc2VsZWN0IChpbiB0aGlzIGNhc2UpIGNlcnRhaW4gY2hhcmFjdGVycywgdGhlaXIgY29ubmVjdGl2aXR5IGNoYXJhY3RlcmlzdGljcywgYW5kIHRoZWlyIGVudmlyb21lbnQuIA0KDQpGaXJzdCB3ZSBsb29rIGF0IGRpZmZlcmVudCBtZWFzdXJlcyBvZiBkZWdyZWUtY2VudHJhbGl0eSwgd2hpY2ggYXJlIGEgc2V0IG9mIG1lYXN1cmVzIGluY2ljYXRpbmcgYSBjZXJ0YWluIHR5cGUgb2Ygc3RydWN0dXJhbCBpbXBvcnRhbmNlIGluIHRoZSBuZXR3b3JrLg0KDQojIyMjIERlZ3JlZSBjZW50cmFsaXR5DQoNClRoZSBmaXJzdCBvbmUgaXMgdGhlIGRlZ3JlZSBjZW50cmFsaXRpZXMgaXMgdGhlIGRlZ3JlZSBjZW50cmFsaXR5LCB3aGljaCBwbGFpbmx5IG1lYW5zIGhvdyB3ZWxsIGNvbm5lY3RlZCB0aGUgbm9kZSBpcyAoPSBOdW1iZXIgb2YgRWRnZXMpLiBUaGUgdmVyc2lvbiBmb3IgdGhlIHdlaWdodGVkIG5ldHdvcmtzICg9IFN1bSBvZiBlZGdld2VpZ3RocykgY2FuIGJlIGFjY2Vzc2VkIHdpdGggYHN0cmVuZ3RoKClgLiBXZSBjYW4gYWxzbyBkaXJlY3RseSBjaGVjayB3aGljaCBub2RlIGhhcyB0aGUgbWF4aW11bSBkZWdyZWUuDQoNCmBgYHtyfQ0KZGVncmVlKGcpIA0Kd2hpY2gubWF4KGRlZ3JlZShnKSkNCg0Kc3RyZW5ndGgoZykNCndoaWNoLm1heChzdHJlbmd0aChnKSkNCmBgYA0KDQpXZWxsLCBhZ2FpbiBUeXJpb24gaXQgaXMuLi4NCg0KIyMjIyBFaWdlbnZlY3RvciBDZW50cmFsaXR5DQoNCkFnYWluLCB0aGUgZWlnZW52ZWN0b3IuIEVpZ2VudmVjdG9yIGNlbnRyYWxpdHkgaXMgYSB2ZXJ5IGludGVyZXN0aW5nIG1lYXN1cmUuIFRoZSBpZGVhIGlzIHRoYXQgbm9kZXMgYXJlIHRoZSBtb3JlIGltcG9ydGFudCB3aGVuIHRoZXkgYXJlIGNvbm5lY3RlZCB0byBtb3JlIGltcG9ydGFudCBub2Rlcy4gU28sIGlmIHlvdSBoYXZlIGNvb2wgZnJpZW5kcywgeW91IGFyZSBhbHNvIHN1cHBvc2VkIHRvIGJlIHNvbWV3aGF0IGNvb2xlci4gWW91IGFscmVhZHkgc2VlLCB0aGUgY2FsY3VsYXRpb24gb2Ygc3VjaCB2YWx1ZXMgaW4gYSBuZXR3b3JrIGJlY29tZXMgY2lyY3VsYXIsIHRoZXJlZm9yZSB3ZSBuZWVkIHNvbWUgbWF0aGVtYXRpY2FsIG1hZ2ljLCB3aGljaCB0aGUgZWlnZW52ZWN0b3IgZG9lcy4gV2Ugd2lsbCBkaWcgaW50byB0aGlzIGNvbmNlcHQgZGVlcGVyIGF0IGFub3RoZXIgcG9pbnQuIFdlIHNjYWxlIGl0LCBzaW5jZSB0aGVzZSB2YWx1ZXMgb3RoZXJ3aXNlIHRlbmQgdG8gYmVjb21lIHZlcnkgbGFyZ2UuIA0KDQoqKk5vdGU6KiogSGVyZSwgYWxzbyBhIHdlaWdodGVkIHZlcnNpb24gaXMgYXZhaWxhYmxlLiBBZ2FpbiwgdGhlIGA/YCBpcyB5b3VyIGZyaWVuZC4NCg0KYGBge3J9DQplaWdlbl9jZW50cmFsaXR5KGcsIHNjYWxlID0gVFJVRSkkdmVjdG9yICU+JSByb3VuZCgzKQ0KYGBgDQoNCg0KIyMjIyBCZXR3ZWVubmVzcyBDZW50cmFsaXR5DQoNCkxhc3RseSwgdGhlIGJldHdlZW5uZXNzIGNlbnRyYWxpdHkuIFRoYXQgaXMgYWxzbyBhbiB2ZXJ5IGludGVyZXN0aW5nIGNvbmNlcHQuIFRoaXMgb25lIGlzIGEgbWVhc3VyZSBvZiBob3cgbXVjaCBhIG5vZGUgY29ubmVjdHMgb3RoZXJ3aXNlIHVuY29ubmVjdGVkIG5vZGVzIHdpdGggZWFjaCBvdGhlcnMuIFRoaXMgaXMgbWVhc3VyZWQgYnkgdGhlIGFtb3VudCBvZiAqKnNob3J0ZXN0IHBhdGhzKiogbGVhZGluZyB0aHJvdWdoIHRoZSBub2RlLg0KDQohW10oLi4vbWVkaWEvTTJfMV9zaG9ydHBhdGgucG5nKXt3aWR0aD0yNTBweH0NCg0KDQoNCg0KDQoNCg0KDQoNCmBgYHtyfQ0KYmV0d2Vlbm5lc3MoZykNCmBgYA0KDQoNCiMjIyMgTmVpZ2hib3Job29kIG9mIGEgTm9kZQ0KDQpMYXN0bHksIHdlIGNhbiBsb29rIGF0IHRoZSBzdXJyb3VuZGluZyBvZiBhIG5vZGUsIG1lYW5pbmcgdGhlIG9uZXMgaXQgaXMgY29ubmVjdGVkIHRvLCBpdHMgKipuZWlnaGJvcmhvb2QqKi4NCg0KYGBge3J9DQpuZWlnaGJvcnMoZywgJ1JvYmVydCBCYXJhdGhlb24nKQ0KYGBgDQoNCkxpa2V3aXNlLCB3ZSBjYW4gbG9vayBhdCB0aGUgKiplZ28tbmV0d29yayBvZiBhIG5vZGUqKi4gVGhhdCBtZWFucyBob3cgbWFueSBub2RlcyBhcmUgaW4gYSBjZXJ0YWluICoqZ2VvZGVzaWMgZGlzdGFuY2UqKi4gUGxhaW5seSBzcGVha2luZywgaG93IG1hbnkgbm9kZXMgYXJlIG5vdCBtb3JlIHRoYW4geC1zdGVwcyBhd2F5Lg0KDQohW10oLi4vbWVkaWEvTTJfMV9kaXN0YW5jZS5qcGcpe3dpZHRoPTI1MHB4fQ0KDQpgYGB7cn0NCmVnbyhnLCAyLCAiRHJvZ28iKVtbMV1dDQpgYGANCg0KV2UgY2FuIGFsc28gbm90IG9ubHkgbG9vayBhdCBpdCwgYnV0IHByb2R1Y2UgYSBuZXcgc3ViLWdyYXBoIG9ubHkgb2YgdGhpcyBlZ28tbmV0d29yay4NCg0KYGBge3J9DQpnLmRyb2dvIDwtIG1ha2VfZWdvX2dyYXBoKGcsIDIsIG5vZGVzID0gIkRyb2dvIilbWzFdXQ0KZy5kYW5ueSA8LSBtYWtlX2Vnb19ncmFwaChnLCAyLCBub2RlcyA9ICJEYWVuZXJ5cyBUYXJnYXJ5ZW4iKVtbMV1dDQpgYGANCg0KYGBge3J9DQpwbG90KGcuZHJvZ28pDQpwbG90KGcuZGFubnkpDQpgYGANCg0KV2VsbCwgRGFubnkgc2VlbXMgdG8gYmUgd2F5IG1vcmUgY29ubmVjdGVkIHRoYW4gaGVyIGh1c2JhbmQsIHJpZ2h0Pw0KDQpCdHc6IFRvIG1lcmdlIHR3byBncmFwaHMsIGp1c3QgZG86DQoNCmBgYHtyfQ0KZy5tZXJnZSA8LSBnLmRyb2dvICsgZy5kYW5ueQ0KZy5tZXJnZQ0KYGBgDQoNCg0KIyMjIChHbG9iYWwpIE5ldHdvcmsgc3RydWN0dXJlDQoNCkZpbmFsbHksIGl0IGlzIG9mdGVuIGFsc28gaW5mb3JtYXRpdmUgdG8gbG9vayBhdCB0aGUgb3ZlcmFsIGNoYXJhY3RlcmlzdGljcyBvZiB0aGUgbmV0d29yay4gV2Ugd2lsbCBkbyB0aGlzIGluIG1vcmUgZGV0YWlsIGVueHQgdGltZSwgYnV0IGp1c3Qgc28geW91IGtub3c6DQoNCg0KVGhlICoqZGVuc2l0eSoqIG9mIGEgbWVhc3VyZSByZXByZXNlbnRzIHRoZSBzaGFyZSBvZiBhbGwgY29ubmVjdGVkIHRvIGFsbCBwb3NzaWJsZSBjb25uZWN0aW9ucyBpbiB0aGUgbmV0d29yaw0KDQpgYGB7cn0NCmVkZ2VfZGVuc2l0eShnKQ0KYGBgDQoNCioqVHJhbnNpc3Rpdml0eSoqLCBhbHNvIGNhbGxlZCB0aGUgKipDbHVzdGVyaW5nIENlZmZpY2llbnQqKiBpbmRpY2F0ZXMgaG93IG11Y2ggdGhlIG5ldHdvcmsgdGVuZHMgdG8gYmUgbG9jYWxseSBjbHVzdGVyZWQuIFRoYXQgaXMgbWVhc3VyZWQgYnkgdGhlIHNoYXJlIG9mICoqY2xvc2VkIHRyaXBsZXRzKiouIEFnYWluLHcgZSB3aWxsIGRpZyBpbnRvIHRoYXQgbmV4dCB0aW1lLg0KDQohW10oLi4vbWVkaWEvTTJfMV9jY29lZmYucG5nKXt3aWR0aD0yNTBweH0NCg0KDQpgYGB7cn0NCnRyYW5zaXRpdml0eShnKQ0KYGBgDQoNCg0KVGhlICoqZGlhbWV0ZXIqKiBpcyB0aGUgbG9uZ2VzdCBvZiB0ZWggc2hvcnRlc3QgcGF0aHMgYmV0d2VlbiB0d28gbm9kZXMgb2YgdGhlIG5ldHdvcmsuDQoNCmBgYHtyfQ0KZGlhbWV0ZXIoZywgZGlyZWN0ZWQgPSBGLCB3ZWlnaHRzID0gTkEpDQpgYGANCg0KRmluYWxseSwgdGhlICoqbWVhbiBkaXN0YW5jZSoqLCBvciAqKmF2ZXJhZ2UgcGF0aCBsZW5naHQqKiByZXByZXNlbnRzIHRoZSBtZWFuIG9mIGFsbCBzaG9ydGVzdCBwYXRocyBiZXR3ZWVuIGFsbCBub2Rlcy4gSXQgaXMgYSBtZWFzdXJlIG9mIGRpZmZ1c2lvbiBwb3RlbnRpYWwgd2l0aGluIGEgbmV0d29yay4NCg0KYGBge3J9DQptZWFuX2Rpc3RhbmNlKGcsIGRpcmVjdGVkID0gRikNCmBgYA0KDQojIyBZb3VyIHR1cm4NCkFoaCwgeW91IHNhdyBpdCBjb21taW5nLCByaWdodD8gV2hhdCBhYm91dCB5b3UgZXhwbG9yZSB0aGUgR29UIG5ldHdvcmsgYSBiaXQgb24geW91ciBvd24gW0hFUkVdKGh0dHBzOi8vd3d3LmthZ2dsZS5jb20vZGFuaWVsaGFpbi9zZHMtMjAxOC1tMi0xLWludHJvLW53LWV4ZXJjaXNlLTEpLiBMZXRzIHNlZSBob3cgdGhhdCB3b3JrcyBvdXQhDQoNCg0KDQojIERpcmVjdGVkIE5ldHdvcmtzIGFyZSBjb21taW5nLi4uDQoNClNvIGZhciBzbyBnb29kLCB1cCB0byBub3cgd2UgY29uc2lkZXJlZCB1bmRpcmVjdGVkIG5ldHdvcmtzLCBjb25zdHJ1Y3RlZCBieSB0aGUgYW1vdW50IGNoYXJhY3RlcnMgY28tb2NjdXIuIEhvd2V2ZXIsIGFzIHlvdSBhbHJlYWR5IG1pZ2h0IGd1ZXNzLCB0aGF0J3Mgbm90IHdoZXJlIHdlIHN0b3AuIFNPbWUgZ2VuZXJhbCBpbmZvcyBvbiBkaXJlY3RlZCBuZXR3b3JrczoNCg0KKiBSZWxhdGlvbnMgZG8gbm90IG5lY2Vzc2FyaWx5IGhhdmUgdG8gYmUgc3ltbWV0cmljLiBSYXRoZXIsIG9mdGVuIHdlIGZpbmQgYSBsb2dpY2FsIG9yIGVtcGlyaWNhbCBkaXJlY3Rpb24gaW4gcm9sZSBiYXNlZCwgYWZmZWN0aXZlIGFuZCBpbnRlcmFjdGl2ZSByZWxhdGlvbnNoaXBzLg0KKiBFZy4gaXMgc3VwZXJ2aXNvciBvZi4uLiwgZ2l2ZXMgYWR2aWNlIHRvLi4uLCBpcyBzdXBwbGllciBvZi4uLiwgaW52ZXN0cyBpbiAuLi4NCiogVGhpcyBkaXJlY3Rpb24gaXMgb2Z0ZW4gY3J1Y2lhbCBmb3IgdGhlIGNvcnJlY3QgaW50ZXJwcmV0YXRpb24NCiogSW50cm9kdWNlcyBuZXcgbWVhc3VyZW1lbnRzLCBlZy4gdGhlIGRpZmZlcmVudGlhdGlvbiBvZiBkZWdyZWVzIGludG8gb3V0LSAoc2VuZGluZyBhIHRpZSkgYW5kIGluLWRlZ3JlZXMgKHJlY2VpdmluZyBhIHRpZSkNCg0KQW4gb2J2aW91cyBleGFtcGxlIGF0IHRoZSBHb1QgY2FzZSBhcmUgZmFtaWx5IHRpZXMuIEhlcmUsIEkgd2lsbCBvc2UgdGhlIG5pY2VseSBjb21waWxlZCBkYXRhc2V0IG9mIHRoZSB3b25kZXJmdWwgW1NoaXJpbl0oaHR0cHM6Ly9zaGlyaW5nLmdpdGh1Yi5pbykgdGhhdCBjYW4gYmUgZm91bmQgW2hlcmVdKGh0dHBzOi8vZ2l0aHViLmNvbS9TaGlyaW5HL2Jsb2dfcG9zdHNfcHJlcC90cmVlL21hc3Rlci9Hb1QpLiBJdCBjb250YWlucyBhIG5vZGVsaXN0IHdpdGggaG91c2UtYWZmaWxpYXRpb25zIGFuZCBmdXJ0ZWhyIGNoYXJhY3RlcmlzdGljcyBvZiBtYWluIGNoYXJhY3RlcnMsIGFuZCBhIGVkZ2VsaXN0IG9mIHRoZWlyIGZhbWlseSByZWxhdGlvbnNoaXBzLg0KDQojIyBMb2FkIHRoZSBncmFwaA0KDQpgYGB7cn0NCnJtKGNoYXJzLm1haW4sIGcsIGcuZGFubnksIGcuZHJvZ28sIGcubWVyZ2UpDQplZGdlcy5mYW0gPC0gcmVhZFJEUygiLi4vaW5wdXQvR29UL3VuaW9uX2VkZ2VzLlJEUyIpDQpub2Rlcy5mYW0gPC0gcmVhZFJEUygiLi4vaW5wdXQvR29UL3VuaW9uX2NoYXJhY3RlcnMuUkRTIikNCmBgYA0KDQpgYGB7cn0NCmhlYWQobm9kZXMuZmFtKQ0KaGVhZChlZGdlcy5mYW0pDQpgYGANCg0KTGV0cyBjb25zdHJ1Y3QgdGVoIGdyYXBoLiBXZSBub3cgYWxzbyBmZWVkIGluIGEgc2V0IG9mIG5vZGVzIHdpdGggdGhlaXIgY2hhcmFjdGVyaXN0aWNzLg0KDQpgYGB7cn0NCmcgPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGVkZ2VzLmZhbSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICB2ZXJ0aWNlcyA9IG5vZGVzLmZhbSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpcmVjdGVkID0gVFJVRSkNCmcNCmBgYA0KDQojIyBWaXN1YWxpemluZyBuZXR3b3JrcyBJDQoNCkhvdyBkb2VzIHRoZSBwbG90IGxvb2s/DQoNCmBgYHtyfQ0KcGxvdChnKQ0KYGBgDQoNCldlbGwsIHRoYXRzIHNvbWUgdW5pbmZvcm1hdGl2ZSBoYWlyYmFsbC4gU3VjaCB0aGluZ3Mgb2Z0ZW4gaGFwcGVuIHdoZW4gd2Ugd2FudCB0byBwbG90IGxhcmdlIG5ldHdvcmtzLiBUaGlzIGlzIGEgZ29vZCBwb2ludCB0byBzdGFydCB1c2luZyB0aGUgcGFyYW1ldGVycyBpbiB0aGUgYGlncmFwaGAgcGxvdHRpbmcgZnVuY3Rpb24uIE5leHQgdGltZSBJIHdpbGwgaW50cm9kdWNlIHlvdSB0byBteSBjdXJyZW50IGZhdm9yaXRlLCBgZ2dyYXBoYC4gSG93ZXZlciwgdGhlIGBpZ3JhcGhgIHBsb3R0aW5nIGZ1bmN0aW9uIGlzIHJlbGF0aXZlbHkgZWFzeSB0byBzdWUuIHNvIGl0cyB3b3J0aCAoaWYgb25seSBmb3IgdGhlIHNha2Ugb2YgaWxsdXN0cmF0aW9uKSB0byB0d2VhayB0aHJvdWdoIGFsbCB0aGUgcGFyYW1ldGVycyB0byBnZXQgVEhFIEdvVCBmYW1pbHkgZ3JhcGgsIGFzIHByZXR0eSBhcyBwb3NzaWJsZS4NCg0KRm9yIHBsb3R0aW5nIHRoZSBsZWdlbmQsIEkgYW0gc3VtbWFyaXppbmcgdGhlIGVkZ2UgYW5kIG5vZGUgY29sb3JzIHVwZnJvbnQuIFlvdSB3aWxsIGxhdGVyIHNlZSB3aHkuDQoNCmBgYHtyfQ0KY29sb3JfdmVydGljZXMgPC0gbm9kZXMuZmFtICU+JQ0KICBncm91cF9ieShob3VzZSwgY29sb3IpICU+JQ0KICBzdW1tYXJpc2UobiA9IG4oKSkgJT4lDQogIGZpbHRlcighaXMubmEoY29sb3IpKQ0KDQpjb2xvcnNfZWRnZXMgPC0gZWRnZXMuZmFtICU+JQ0KICBncm91cF9ieSh0eXBlLCBjb2xvcikgJT4lDQogIHN1bW1hcmlzZShuID0gbigpKSAlPiUNCiAgZmlsdGVyKCFpcy5uYShjb2xvcikpDQpgYGANCg0KT2ssIHdlIGFyZSByZWFkeSwgbGV0cyBkbyB0aGlzIHBsb3QhDQoNCmBgYHtyLCBmaWcud2lkdGg9MTUsIGZpZy5oZWlnaHQ9MTV9DQpwbG90KGcsDQogICAgIGxheW91dCA9IGxheW91dF93aXRoX2ZyKGcpLCAjIGdyYXBoIGxheW91dCwgbW9yZSBvbiB0aGF0IGxhdGVyDQogICAgIHZlcnRleC5sYWJlbCA9IGdzdWIoIiAiLCAiXG4iLCBWKGcpJG5hbWUpLCAjIEp1c3QgYWx0ZXJlZCB0aGUgbGFiZWwgdGhhdCBpdCBpcyBpbiB0d28gbGluZXMNCiAgICAgdmVydGV4LnNoYXBlID0gVihnKSRzaGFwZSwgIyBsb2FkIHRoZSBwcmVkZWZpbmVkIHNoYXBlIG9mIHRoZSBub2RlcyAobWFsZS9mZW1hbGUpDQogICAgIHZlcnRleC5jb2xvciA9IFYoZykkY29sb3IsICMgbG9hZCB0aGUgcHJlZGVmaW5lZCBjb2xvciBvZiB0aGUgbm9kZXMgKGhvdXNlcykNCiAgICAgdmVydGV4LnNpemUgPSAoVihnKSRwb3B1bGFyaXR5ICsgMC41KSAqIDUsICMgZGVmaW5lIG5vZGUtc2l6ZSBieSBwb3B1bGFyaXR5DQogICAgIHZlcnRleC5mcmFtZS5jb2xvciA9ICJncmF5IiwgIyBjb2xvciBvZiB0aGUgZnJhbWUgYXJvdW5kIHRoZSBub2RlDQogICAgIHZlcnRleC5sYWJlbC5jb2xvciA9ICJibGFjayIsICMgY29sb3Igb2YgdGhlIGxhYmVsDQogICAgIHZlcnRleC5sYWJlbC5jZXggPSAwLjgsICMgc2l6ZSBvZiB0aGUgbGFiZWwNCiAgICAgZWRnZS5hcnJvdy5zaXplID0gMC41LCAjIHNpemUgb2YgdGhlIGFycm93DQogICAgIGVkZ2UuY29sb3IgPSBFKGcpJGNvbG9yLCAjIGxhb2QgcHJlZGVmaW5lZCBlZGdlL2NvbG9yIChyZWxhdGlvbnNoaXApDQogICAgIGVkZ2UubHR5ID0gRShnKSRsdHkpICMgRWRnZSBzdHlsZQ0KbGVnZW5kKCJ0b3BsZWZ0IiwgbGVnZW5kID0gYyhOQSwgIk5vZGUgY29sb3I6IiwgYXMuY2hhcmFjdGVyKGNvbG9yX3ZlcnRpY2VzJGhvdXNlKSwgTkEsICJFZGdlIGNvbG9yOiIsIGFzLmNoYXJhY3Rlcihjb2xvcnNfZWRnZXMkdHlwZSkpLCBwY2ggPSAxMCwNCiAgICAgICBjb2wgPSBjKE5BLCBOQSwgY29sb3JfdmVydGljZXMkY29sb3IsIE5BLCBOQSwgY29sb3JzX2VkZ2VzJGNvbG9yKSwgcHQuY2V4ID0gMywgY2V4ID0gMiwgYnR5ID0gIm4iLCBuY29sID0gMSwNCiAgICAgICB0aXRsZSA9ICIiKSANCmxlZ2VuZCgidG9wbGVmdCIsIGxlZ2VuZCA9ICIiLCBjZXggPSAzLCBidHkgPSAibiIsIG5jb2wgPSAxLA0KICAgICAgIHRpdGxlID0gIkdhbWUgb2YgVGhyb25lcyBGYW1pbHkgVGllcyIpDQpgYGANCg0KV2hhdCBhIGJlYXV0eSEgVGhhbmtzIHRvIFNoaXJpbidzIG5pY2UgdXBmcm9udCB3b3JrLCBpdCB3YXMgcmF0aGVyIGVhc3kgdG8gcGxvdCBpdCB0aGF0IG5pY2VseS4gSG93ZXZlciwgd2UgY291bGQgYWxzbyBkZWZpbmUgb3VyIGNvbG9ycyBhcyB3ZSB3aXNoZWQuIEhlcmUgdGhlICBbUi1Db2xvciBQYWxldHRlc10oaHR0cHM6Ly93d3cubmNlYXMudWNzYi5lZHUvfmZyYXppZXIvUlNwYXRpYWxHdWlkZXMvY29sb3JQYWxldHRlQ2hlYXRzaGVldC5wZGYpIG1pZ2h0IGJlY29tZSBoYW5keS4NCg0KDQojIyBDb21tdW5pdHkgRGV0ZWN0aW9uDQoNCllvdSBtaWdodCBoYXZlIGFscmVhZHkgZ3Vlc3NlZCwgd2UgY2FuIHZlcnkgd2VsbCBhbHNvIGRvIGEgY2x1c3RlcmluZyBleGVyY2lzZSBpbiBuZXR3b3Jrcy4gSGVyZSwgd2UgZG8gbm90IGNsdXN0ZXIgbm9kZXMgYWNjb3JkaW5nIHRvIHRoZWlyIHNpbWlsYXJpdHkgaW4gYXR0cmlidXRlcywgYnV0IGFjY29yZGluZyB0byB0aGVpciBjb25uZWN0aXZpdHkuIFRoZXJlIGFyZSBwbGVudHkgb2YgYWxnb3JpdGhtcywsIGFuZCB3ZSB3aWxsIGV4cGxvcmUgZnVydGhlciBvbmVzIGxhdGVyb24uIE1vc3Qgb2YgdGhlbSBhaW0gdG8gZmluZCBjb21tdW5pdGllcyB3aXRoIG1heGltdW0gd2l0aGluL2Nvbm5lY3Rpdml0eSwgYW5kIG1pbmltdW0gYmV0d2Vlbi9jb25uZWN0aXZpdHkuDQoNCkhvd2V2ZXIsIG1vc3Qgb2YgdGhlbSBhcmUgbm90IGRlc2lnbmVkIHRvIHdvcmsgd2l0aCBkaXJlY3RlZCBuZXR3b3Jrcy4gVGhlcmVmb3JlLCB3ZSB3aWxsIGNvbnZlcnQgb3VyIG5pY2UgbmV0d29yayBmb3Igbm93IHRvIGFuIHVuZGlyZWN0ZWQgb25lLg0KDQpgYGB7cn0NCmcudWQgPC0gYXMudW5kaXJlY3RlZChnKQ0KYGBgDQoNCkZpcnN0LCB3ZSB3aWxsIGdpdmUgaXQgYSB0cnkgd2l0aCB0aGUgKiplZGdlLWJldHdlZW5uZXNzKiogYWxnb3JpdGhtIChOZXdtYW4tR2lydmFuKS4gSGVyZSwgaGlnaC1iZXR3ZWVubmVzcyBlZGdlcyBhcmUgcmVtb3ZlZCBzZXF1ZW50aWFsbHkgKHJlY2FsY3VsYXRpbmcgYXQgZWFjaCBzdGVwKSBhbmQgdGhlIGJlc3QgcGFydGl0aW9uaW5nIG9mIHRoZSBuZXR3b3JrIGlzIHNlbGVjdGVkLg0KDQpMZXRzIHRha2UgYSBsb29rIGhvdyBpdCB3b3Jrcy4NCg0KYGBge3J9DQo/Y2x1c3Rlcl9lZGdlX2JldHdlZW5uZXNzDQpgYGANCg0KQW5kIHdlIG5vdyBydW4gaXQuIEFzIGFuIGhpcmFyY2hpY2FsIGNvbW11bml0eSBkZXRlY3Rpb24gdGVjaG5pcXVlLiBTaW5jZSBpdCBpcyBhbiBoaXJhcmNoaWNhbCBvbmUsIHdlIGNhbiBhZ2FpbiBwbG90IGEgZGVuZG9ncmFtIHdoaWNoIHdlIGFscmVhZHkga25vdyBmcm9tIHRoZSBoaXJhcmNoaWNhbCBjbHVzdGVyaW5nDQoNCmBgYHtyLCBmaWcud2lkdGg9MzAsIGZpZy5oZWlnaHQ9MTV9DQoNCmNlYiA8LSBjbHVzdGVyX2VkZ2VfYmV0d2Vlbm5lc3MoZy51ZCkgDQpkZW5kUGxvdChjZWIsIG1vZGU9ImhjbHVzdCIpDQpgYGANCg0KYGBge3IsIGZpZy53aWR0aD0yMCwgZmlnLmhlaWdodD0yMH0NCnBsb3QoY2ViLCBnLnVkLA0KICAgICB2ZXJ0ZXguZnJhbWUuY29sb3IgPSBWKGcpJGNvbG9yLCAjIGxvYWQgdGhlIHByZWRlZmluZWQgY29sb3Igb2YgdGhlIG5vZGVzIChob3VzZXMpDQogICAgIHZlcnRleC5zaXplID0gKFYoZykkcG9wdWxhcml0eSArIDAuNSkgKiA1ICMgZGVmaW5lIG5vZGUtc2l6ZSBieSBwb3B1bGFyaXR5KSANCikNCmBgYA0KDQpMZXRzIG9ubHkgc2VlIGhvdyBnb29kIGl0IHBlcmZvcm1zIG9uIHRoZSBtYWpvciBob3VzZXMsIHRoZSByZXN0IGlzIHRvbyBzbWFsbCBhbnlob3cNCg0KYGBge3J9DQpiaW5kX2NvbHMoY29tID0gY2ViJG1lbWJlcnNoaXAsIGhvdXNlID0gVihnLnVkKSRob3VzZSkgJT4lDQogIGdyb3VwX2J5KGhvdXNlKSAlPiUNCiAgZmlsdGVyKG4oKSA+PSAxMCkgJT4lDQogIHVuZ3JvdXAoKSAlPiUNCiAgdGFibGUoKQ0KYGBgDQoNCldlIHNlZSwgaW5kZWVkLCB0aGF0IHRoZSBjb21tdW5pdGllcyBmb3IgdGhlIG1vc3QgcGFydCBjYXB0dXJlIHRoZSBhZmZpbGlhdGlvbiB0byB0aGUgZ3JlYXQgaG91c2VzLg0KDQojIyBZb3VyIHR1cm4NCg0KQUdhaW4sIGl0cyB0aW1lIHRvIGhhdmUgc29tZSBmdW4gb24geW91ciBvd24uIFtIRVJFXShodHRwczovL3d3dy5rYWdnbGUuY29tL2RhbmllbGhhaW4vc2RzLTIwMTgtbTItMS1pbnRyby1udy1leGVyY2lzZS0yKSB5b3Ugd2lsbCBmaW5kIGFub3RoZXIga2FnZ2xlIG5vdGVib29rIHdoZXJlIHlvdSBjYW4gZGVtb25zdHJhdGUgeW91ciBuZXR3b3JrIGFuYWx5c2lzIHNraWxscyBldmVuIG1vcmUhDQoNCg==